高階関数(fold)

前回mapについてやったので今回はfoldという高階関数について説明します。 英語ではfoldは「折りたたむ」といったような意味の単語ですが foldでの「折りたたむ」というのは 集合の各要素に演算を行い、値に縮める、といったような意味合いになります。 ※以下、集合にはリストを用いて説明します 例えば「リストの和」を考えてみると  入力:[1; 2; 3; 4; 5; 6; 7; 8; 9; 10]  出力:55 元々はint値の集合(int list)だったものが、int値になっています。 そして、このような演算を抽象化したのが、fold関数になります。 なお、縮めた値自体が集合の場合もあるので 出力の型は入力の型よりもシンプルになるとは限りません (例えばこの後の例で出てくるrevは(int list -> int list)) foldは、計算順序によって2種類にわけられます。
List.fold_left
('state -> 'a -> 'state) -> 'state -> 'a list -> 'state 第1引数をf、第2引数をinit、 第3引数を[l1;l2;..;ln]と呼ぶことにすると fold_leftは次の計算をします f (... (f (f (f init l1) l2) l3) ... ln) 例:fold_left (fun x y->x+y) 0 [1..3]は((0+1)+2)+3を計算
List.fold_right
('a -> 'state -> 'state) -> 'a list -> 'state -> 'state 第1引数をf、第2引数を[l1;..;ln-1;ln]、 第3引数をinitと呼ぶことにすると fold_rightは次の計算をします f l1 (... (f ln-1 (f ln init)) ...) 例:fold_right (fun x y->x+y) [1..3] 0は1+(2+(3+0))を計算
Listモジュールには、リストを2つに拡張した版 (fold_left2など)もあるようです。 参考:Module Microsoft.FSharp.Collections.List foldを使いこなすには、 foldの第1引数の関数引数の意味もちゃんと覚えておく必要があります。 第1引数の関数は2引数関数ですが、これに渡るのは (これまでのfold演算の累積値)と(リストの要素)です。 累積値のほうをacc、リストの要素をxと呼ぶとすると initはaccのほうに、リストの要素はxのほうに渡ります。 また、fold_leftとfold_rightではaccとxの順番が異なっていて fold_leftの第1引数はf acc x fold_rightの第1引数はf x acc となるので注意してください。 ※このあたりは、各関数型言語ごとに異なるようなので覚えるのが大変 foldは非常に便利なのですが、中々わかりにくい関数なので どんな場合にfoldが使えるのかというイメージをもってもらうために foldを使って書き換えが可能な関数を挙げてみます。
foldで書き直せる関数
//リストの長さを返す
let rec count = function
    | [] -> 0
    | x::xs -> 1 + (count xs);;
//リストの要素の和を返す
let rec sum = function
    | [] -> 0
    | x::xs -> x + (sum xs);;
//リストを逆順にする。
//::でなく@を使っているのがポイント
let rec rev = function
    | [] -> []
    | x::xs -> (rev xs) @ [x];;
見たらわかるように、これらはどれも同じようなパターンの定義です。 こういう定型的なパターンはfoldを使うことで書き直すことが出来ます。
foldを用いて書き直した例
//機械的に書き直した物
let count ls = List.fold_left (fun acc x -> 1+acc) 0 ls;;
let sum ls = List.fold_left (fun acc x -> x+acc) 0 ls;;
let rev ls = List.fold_right (fun x acc -> acc @ [x]) ls [];;
//foldを使うと::でも定義出来る
let rev ls = fold_left (fun acc x -> x::acc) [] ls;;
fold_leftとfold_rightの動作のサンプルです。
fold_leftとfold_right
List.fold_right (fun x y -> x^y) ["a";"b";"c"] "R";;
List.fold_right (fun x y -> y^x) ["a";"b";"c"] "R";;
List.fold_left  (fun x y -> x^y) "L" ["a";"b";"c"];;
List.fold_left  (fun x y -> y^x) "L" ["a";"b";"c"];;

List.fold_left (fun x y -> y::x) [0] [1..3];;
List.fold_right (fun x y-> x::y) [1..3] [0];;
//List.fold_left (fun x y -> x::y) [0] [1..3];; //これはエラー
//List.fold_right (fun x y-> y::x) [1..3] [0];; //これはエラー
上記コードのインタプリタでの実行結果(上から順に)
val it : string = "abcR"
val it : string = "Rcba"
val it : string = "Labc"
val it : string = "cbaL"
val it : int list = [3; 2; 1; 0]
val it : int list = [1; 2; 3; 0]
実はmapもfoldを用いて定義出来ます。
mapをfoldで定義
//mapをfold_leftで定義したもの
let mmap f ls = rev <| fold_left (fun acc x -> (f x)::acc) [] ls;;	
//tail側から実行するmap
let mmapr f ls = fold_right (fun x acc -> (f x)::acc) ls [];;
//テスト実行
let f x = printfn "%d" x;x in
let ls = [1..3] in
List.map f ls;mmap f ls;mmapr f ls;;
さらに、もうちょっと複雑な例
もうちょっと複雑な例
//順列組み合わせを求める(重複がある場合は動作しない)
let permutation lst =
    let rec p a b = function
        | [] -> a::b
        | ls -> fold_left (fun x y -> p (y::a) x (filter ((<>)y) ls)) b ls in
    p [] [] lst;;
permutation [1..3];;
全然個人的な感想ですが 順列やら組み合わせやらを生成する関数は 富豪的なところが好きです。 最後にfoldの実装例を挙げてみます。 fold_leftは末尾再帰の形ですが fold_rightはそうではないため 処理効率的にはfold_leftのほうが有利になります。
foldの実装例
let rec foldl f init = function
    | [] -> init
    | x::xs -> foldl f (f init x) xs;;
let rec foldr f ls init = match ls with
    | [] -> init
    | x::xs -> f x (foldr f xs init);;