Ocamlの畳み込み関数について

Question

前提・実現したいこと

Ocaml で畳み込み関数fold_rightを用いてリストの最大要素を返すプログラムを作成したいのですが分かりません。畳み込み関数がよくわからないのでどなたかプログラムとともにご教授お願い致します。

該当のソースコード

  let max_list  a =
  match a with
  [] -> min_int
  |h::t ->f h(fold_right  a b -> if a > b then a else b);;

Comments

[ozwk]

> 畳み込み関数がよくわからないので

「(出典元)でこういう説明がされているがここがわからない」というような書き方でお願いします。
さもないとそのへんに転がっている説明を焼き直すぐらいしかできません:

[List](https://ocaml.jp/archive/ocaml-manual-3.06-ja/libref/List.html)

> List.fold_right f [a1; ...; an] b は f a1 (f a2 (... (f an b) ...)) です。末尾再帰になっていません。

これを読んでどこがわからないですか?

Answer 1

もうすでに解決済みかもしれませんが、何かの役に立てばと思い、回答します。

畳み込み関数について

畳み込み関数というのは、ざっくりいうと「リストの要素に順番に関数を適用してその結果を蓄積し、最後に蓄積した結果を返す」関数です。

ある整数リストの要素をすべて足した結果を返すsum関数を考えてみましょう。
リストをxs、適用する関数を+（整数の足し算）とすると、こんなイメージです。

let sum xs =
    let acc = 0           (* 初期値は 0 *)
    let x = List.nth xs 1 (* リストから1つ目の要素を取り出す *)
    let acc = acc + x     (* acc と要素 x に関数（ここでは足し算）を適用した結果を acc に覚えておく *)
    let x = List.nth xs 2 (* リストから2つ目の要素を取り出す *)
    let acc = acc + x     (* acc と要素 x に関数を適用した結果を acc に覚えておく *)
    ...                   (* これをリストの要素の数だけ繰り返す *)
    acc                   (* 最後に acc を返す *)

このような「リストからある値に『畳み込む』関数」はよく書きますので、標準のListモジュールにすでに用意されています。

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

引数には「適用する関数」「初期値」「リスト」を渡します。fold_leftとfold_rightで引数の順番が逆になっていますので注意です。

fold_leftはリストの左から（つまりリストの1つ目の要素、2つ目の要素……の順に）、fold_rightは右から（つまりリストの「最後から1つ目」の要素、「最後から2つ目の要素」……の順に）関数を適用していきます。

リストの最大要素を返す関数

ではfold_rightを用いてリストの最大要素を返す関数を書いてみましょう（fold_leftでも同様です）。

まず、欲しい関数の型は以下です。
わかりやすいよう、整数のリストのみ扱うことにしましょう。

val max_of_int_list: int list -> int

リストを引数に渡すと最大の要素が返ってきます。

let max_of_int_list xs =
    let init = List.hd x in    (* 初期値はリストの最初の要素とします *)
    List.fold_right (fun acc x ->
        (* acc（つまり今までで最大の要素）よりも x が大きければ acc を x とします *)
        if acc < x
        then x
        else acc
    ) xs init

これで完成です。

整数以外にも対応させたければ「ある要素が別の要素より大きいかどうか比較する関数」を引数に追加し、以下のようにすればよいでしょう。

val max_of_list: ('a -> 'a -> int) -> 'a list -> 'a

let max_of_list cmp xs =
    let init = List.hd x in    (* 初期値はリストの最初の要素とします *)
    List.fold_right (fun acc x ->
        (* cmp a b は a < b なら負数、a > b なら正数、a = b なら 0 を返す関数 *)
        if (cmp acc x) < 0
        then x
        else acc
    ) xs init

注意点

Listモジュールのfold_rightは末尾再帰ではありませんので、大きなリストに対して使うとスタックオーバーフローする可能性があります。そのときは何回かに分けるか、末尾再帰に書き直しましょう。
fold_leftは末尾再帰です。

また、上記のmax_of_int_listやmax_of_listは初期値として最初の要素を渡しているため、最初の1回の比較は無駄ですし、空リストに対しては例外が発生します。わかりやすさ優先としたので、気になるようなら書き直してください。