この記事は ML Advent Calendar 2015 の 7 日目の記事です。

ML 系言語を含め、多くの関数型言語はリストの畳み込み関数を持っている。動作についてはひとつの言語を知っていれば他の言語で困ることはないのだけれど、引数の取り方が違って迷うことがある。

リストの畳み込み

リストの畳み込みと呼ばれる演算には右畳み込みと左畳み込みがあり、リスト [e1, e2, ..., en] と初期値 z、二項演算 ⊕ に対して以下のように定義される。

右畳み込み: (e1 ⊕ (e2 ⊕ ... (en ⊕ z) ... ))
左畳み込み: (( ... ((z ⊕ e1) ⊕ e2) ⊕ ...) ⊕ en)

右畳み込みはリストの右側の要素から順に取り出して初期値 z と組み合わせていき、左畳み込みはそれを左側の要素から行なう。

末尾呼び出しの最適化があれば、左畳み込みは固定のスタック領域で実行できる。

SML 流

SML 流では右畳み込みも左畳み込みも同じ型をしている。

val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
val foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

つまり、 foldl は先程の定義とは異なり次のような計算をする。末尾再帰で書けることに違いはない。

(en ⊕ ... (e2 ⊕ (e1 ⊕ z)) ...)

この流派では畳み込みの方向を変えても引数の関数は変えなくてもよいという特徴がある。特に、 foldl cons [] xs は rev xs で、 foldr cons [] xs は xs になる。 Standard ML の先祖のひとつである Caldelli ML （VAX ML）はこれらをそれぞれ revfold, fold と呼び、 Scheme （SRFI-1）は fold, fold-right と呼ぶ。

Haskell 流

Haskell 流では畳み込みの初期値が右にあるか左にあるかが、引数の関数の型に表れている。

foldl :: (a -> b -> a) -> a -> [b] -> a
foldr :: (a -> b -> b) -> b -> [a] -> b

R6RS Scheme は SRFI-1 とは異なり、こちらの流派を fold-left, fold-right として採用している。

OCaml 流

OCaml 流では、さらに初期値の右左が畳み込み関数自体の型に表れている。

val fold_left  : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b

F# もこの流派だが、左畳み込みを fold、右畳み込みを foldBack と呼んでいる。

ラベル派

ちなみに OCaml にはラベル付き引数（他の言語でいう名前付き引数）があるので、これを使えば引数の順番は気にしなくてよい。

val fold_left  : f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a
val fold_right : f:('a -> 'b -> 'b) -> 'a list -> init:'b -> 'b

これらは ListLabels モジュールに定義されている。

以下はどれも同じ意味だ。

ListLabels.fold_left ~f:(+) ~init:0 [1; 2; 3]
ListLabels.fold_left ~f:(+) [1; 2; 3] ~init:0
ListLabels.fold_left ~init:0 ~f:(+) [1; 2; 3]
ListLabels.fold_left ~init:0 [1; 2; 3] ~f:(+)
ListLabels.fold_left [1; 2; 3] ~f:(+) ~init:0
ListLabels.fold_left [1; 2; 3] ~init:0 ~f:(+)

さらに畳み込み

リストの定義に戻ってみると以下のようになっている。

type 'a list = [] | (::) of 'a * 'a list

(::) を節点、 [] と要素を葉だと思うと、リスト値は右下に伸びた木構造に見える。

このとき、 [] を適当な値、 (::) を適当な二項演算に置き換えると、ちょうど右畳み込みになる。言い換えると、右畳み込みは、リストと同じ形の構文木の計算の実行結果になる。

同様に、自然数を以下のように定義すると、

type nat = Zero | Succ of nat

let rec fold_nat z f = function
  | Zero -> z
  | Succ n -> f @@ fold_nat z f n

let rec nat_of_int = function
  | 0 -> Zero
  | n when n < 0 -> invalid_arg "nat_of_int"
  | n -> Succ (nat_of_int @@ n - 1)

畳み込みは fold_nat は、初期値（Zero に対応する値）に適当な関数 f を Succ の個数分だけ適用することに対応する。

OCaml だと ppx_deriving をつかうと、このような、帰納的な値のコンストラクタを適当な関数に置き換えるという形の畳み込みを自動生成できる。

ちなみに Church エンコーディングによる表現もこのような畳み込みになっている。

zero = λs. λz. z
succ n = λs. λz. s (n s z)

nil = λc. λn. n
cons x xs = λc. λn. c x (xs c n)

おわりに

Cardelli ML はふつうの畳み込みを fold と呼び、 F# は左から右という、数式を読むときのふつうの順序の畳み込みを fold と呼んでいるのが面白いなあと思っただけで、結論は特にありません。

『関数プログラミング入門 Haskell で学ぶ原理と技法』には畳み込みに関する面白げな話が載っています。圏論的には catamorphism とか始代数とかが関係するんじゃないかと思います。

参考文献

The List structure -- The Standard ML Basis Library
ML under Unix -- Cardelli ML (VAX ML) のマニュアル
20 Data.List -- Haskell 2010 Language Report
SRFI 1: List Library
List utilities -- Revised⁶ Report on the Algorithmic Language Scheme — Standard Libraries —
List -- The OCaml system Documentation and user’s manual
Collections.List モジュール (F#)

foldみぎひだり