高階関数(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種類にわけられます。以前はfold_left/fold_rightという名前だったのですが現在はfold_leftはfold,fold_rightはfoldBackという名前に変わっているようです。

List.fold(旧List.fold_left): ('state -> 'a -> 'state) -> 'state -> 'a list -> 'state 第1引数をf、第2引数をinit、第3引数を[l1;l2;..;ln]と呼ぶことにすると foldは次の計算をします f (... (f (f (f init l1) l2) l3) ... ln) 例：List.fold (+) 0 [1..3]は((0+1)+2)+3を計算

List.foldBack(旧List.fold_right): ('a -> 'state -> 'state) -> 'a list -> 'state -> 'state 第1引数をf、第2引数を[l1;..;ln-1;ln]、第3引数をinitと呼ぶことにすると foldBackは次の計算をします f l1 (... (f ln-1 (f ln init)) ...) 例：List.foldBack (+) [1..3] 0は1+(2+(3+0))を計算

Listモジュールには、リストを2つに拡張した版 (fold2,foldBack2など)もあるようです。参考：List module foldを使いこなすには、 foldの第1引数の関数引数の意味もちゃんと覚えておく必要があります。第1引数の関数は2引数関数ですが、これに渡るのは (これまでのfold演算の累積値)と(リストの要素)です。累積値のほうをacc、リストの要素をxと呼ぶとすると initはaccのほうに、リストの要素はxのほうに渡ります。また、foldとfoldBackではaccとxの順番が異なっていて foldの第1引数はf acc x foldBackの第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 (fun acc x -> 1+acc) 0 ls;;
let sum ls = List.fold (fun acc x -> x+acc) 0 ls;;
let rev ls = List.foldBack (fun x acc -> acc @ [x]) ls [];;
//foldを使うと::でも定義出来る
let rev2 ls = List.fold (fun acc x -> x::acc) [] ls;;

foldとfoldBackの動作のサンプルです。

foldとfoldBack

List.foldBack (fun x y -> x+y) ["a";"b";"c"] "R";;
List.foldBack (fun x y -> y+x) ["a";"b";"c"] "R";;
List.fold  (fun x y -> x+y) "L" ["a";"b";"c"] ;;
List.fold  (fun x y -> y+x) "L" ["a";"b";"c"] ;;

List.fold (fun x y -> y::x) [0] [1..3];;
List.foldBack (fun x y-> x::y) [1..3] [0] ;;
//List.fold (fun x y -> x::y) [0] [1..3];; //これはエラー
//List.foldBack (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]

foldはmapよりも抽象度が高いので、実はmapもfoldを用いて定義出来ます。

mapをfoldで定義

//mapをList.foldで定義したもの
let mmap f ls = rev <| List.fold (fun acc x -> (f x)::acc) [] ls;;	
//tail側から実行するmap
let mmapr f ls = List.foldBack (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 -> List.fold (fun x y -> p (y::a) x (filter ((<>)y) ls)) b ls in
    p [] [] lst;;
permutation [1..3];;

全然個人的な感想ですが順列やら組み合わせやらを生成する関数は富豪的なところが好きです。最後にfoldの実装例を挙げてみます。 List.foldは末尾再帰の形ですが List.foldBackはそうではないため処理効率的にはList.foldのほうが有利になります。

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);;