foldみぎひだり - Qiitaこの記事は ML Advent Calendar 2015 の 7 日目の記事です。 ML 系言語を含め、多くの関数型言語はリストの畳み込み関数を持っている。動作についてはひとつの言語を知っていれば他の言語で困ることはないのだけれど、引数の取り方が違って迷うことがある。 リストの畳み込み リストの畳み込みと呼ばれる演算には右畳み込みと左畳み込みがあり、リスト [e1, e2, ..., en] と初期値 z、二項演算 ⊕ に対して以下のように定義される。 右畳み込み (e1 ⊕ (e2 ⊕ ... (en ⊕ z) ... )) 左畳み込み (( ... ((z ⊕ e1) ⊕ e2) ⊕ ...) ⊕ en) 右畳み込みはリストの右側の要素から順に取り出して初期値 z と組み合わせていき、左畳み込みはそれを左側の要素から行なう。 末尾呼び出しの最適化があれば、左畳み込みは固定のスタック領
