List.fold_right で List.fold_left を書く

　この記事は ML Advent Calendar 2020 の14日目の記事です．

　リストの Church encoding と言えば List.fold_right で表現することが多いように思いますが，果たして List.fold_right だけしか使わずに様々なリストについての再帰関数を表現できるのか疑問に思う人も多いのではないでしょうか？ 本記事では，List.fold_right を用いて List.fold_left を実装する方法を紹介します．後者は末尾再帰なのでわざわざ回りくどいことをせずに直接使った方が良いのはもっともなのですが，foldr/build なんかを考える時に頭の片隅にあると便利かもしれません．

List.fold_right と List.fold_left

　OCaml 標準ライブラリで提供されている List.fold_right とは読んで字のごとくリストを右から畳み込む関数で，例えば [1; 2; 3; 4] みたいなリストがあった時，List.fold_right f [1; 2; 3; 4] accu は f 1 (f 2 (f 3 (f 4 accu)))) を返してくれます．List.fold_left は反対に左から畳み込む関数で，例えば List.fold_left f accu [1; 2; 3; 4] は f (f (f (f accu 1) 2) 3) 4 を返してくれます．

　List.fold_right は末尾再帰になっていないので，OCaml では List.fold_left を用いた方が良いとよく言われます．実装を見てみましょう．

let rec fold_left f accu l =
  match l with
    [] -> accu
  | a::l -> fold_left f (f accu a) l

let rec fold_right f l accu =
  match l with
    [] -> accu
  | a::l -> f a (fold_right f l accu)

fold_left の方の再帰呼び出しは関数の返り値を即座に返しているので末尾再帰最適化が行われるのに対し，fold_right の方は関数の返り値に対して f a を適用しているので最適化ができず，スタックを消費してしまいます． これが Haskell のような言語であれば，計算を途中で打ち切れたり無限リストを扱う時に便利だったり，スペースリークしなかったりと fold_right が輝ける場面もあるのですが，OCaml は基本正格評価なので要らない子扱いされることが多いです．かなしい．

　ただまあ，List.fold_right が完全に要らない子かと言えばそうでもなくて，理論的には面白い性質があります． リストとは空リストに対してコンスを繰り返したものと言うのを思い出せば，List.fold_right f l accu は l のコンスを f に，l の空リストを accu に置き換えた式に対応します． これはかなり綺麗な対応関係で，じゃあそのリストを定義してる所でコンスを f に，空リストを accu に置き換えてやれば計算途中でリストを作れるじゃんって最適化があって，foldr/build と呼ばれています．

また，プログラミング言語理論の研究の文脈で Church encoding と言うのがあって，数値とか真偽値とかみたいなデータを関数だけを使って表して，λ計算の計算能力について議論したりするんですが，その時に 「関数 f と accu を受け取って List.fold_right f l accu の値を返す関数」でリスト l を表現したりもします．組があったらそれでリストを表現できるじゃんと思うかもしれないですが，List.fold_right を使った定義は rank-2 types があったら型が付く嬉しさがあります．

fold_right による fold_left の表現

　そんなこんなで List.fold_right にも理論的な面白さがあるので，明らかにそれを使って書くのは難しそうな List.fold_left も書き直してみようと言うのがこの記事の趣旨です． ちょっと遠くなってしまったので再掲しますが，どうやって下を使って上を書き直したものでしょうか？

let rec fold_left f accu l =
  match l with
    [] -> accu
  | a::l -> fold_left f (f accu a) l

let rec fold_right f l accu =
  match l with
    [] -> accu
  | a::l -> f a (fold_right f l accu)

一番困った点は，fold_left の方ではアキュムレータ accu が再帰呼び出しの度に変化しているのに対し，fold_right の方では完全に固定されてしまっていることです． 再帰呼び出し f a (fold_right f l accu) の際，リストの先頭要素が a であることを知っている f a に fold_right f l accu の accu を書き換えさせてやりたいのですが，どう実現したものでしょうか？

　多分一番自然な実装方法は，fold_left の方でアキュムレータに入るはずだった値を受け取って，fold_left の返り値を返す関数を fold_right で書いてやることです．これなら f a から accu の値を受け渡すことができますね．再帰の都合上引数 l と accu の順序が変わっていることにご注意を．

let rec fold_left f l =
  match l with
  | [] -> fun accu -> (* TODO *)
  | a::l -> fun accu -> (* TODO *)

まず，空リストの場合は普通に accu を返すだけなので，fold_right で生成する関数は恒等関数になります．

let rec fold_left f l =
  match l with
  | [] -> fun accu -> accu
  | a::l -> fun accu -> (* TODO *)

次にコンスの場合ですが，再帰呼び出しで帰ってきた関数に，fold_left で引き回すはずだったアキュムレータを渡してやれば良いです．

let rec fold_left f l =
  match l with
  | [] -> fun accu -> accu
  | a::l -> fun accu -> fold_left f l (f accu a)

よって，これを fold_right に落とし込んでやれば，fold_left を書き換えることができますね．ここでは引数 l と accu の順序を元に戻していることに注意して下さい．

let fold_left f accu l =
  List.fold_right (fun a self accu -> self (f accu a)) l (fun accu -> accu) accu

List.fold_right の定義を見返せば分かるのですが，引数 l がコンス a::l のとき self には List.fold_right で書き直す前の fold_left f l が返していた関数が入ります．

実は rev して fold_right しているだけ？

　List.fold_right を用いて List.fold_left を実装できたのでめでたしめでたし，と言いたいところですが，ちょっと待ってください． List.fold_right に渡した関数 fun a self accu -> self (f accu a)) って3引数関数なのに対して毎回の再帰呼び出しでは2引数しか与えられないので，これは部分適用の状態にあります．この関数に最後の引数が渡されるのは List.fold_right が関数を返した後，つまりリストを最後まで走査した後な訳ですから，リストの長さと同じ数のクロージャが生成されてしまっています．

　副作用とかを無視すると List.fold_left と List.fold_right の間には List.fold_left f accu l = List.fold_right (Fun.flip f) (List.rev l) accu が成り立つので，結局この実装って非末尾再帰でリストを反転して List.fold_right する，かなり迂遠なことをしているのは否めないですね…