質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.48%
OCaml

OCaml(オーキャムル)は、フランスのINRIAが開発した関数型言語MLの一種で、 最新の言語理論の成果が取り入れられているプログラミング言語です。

Q&A

1回答

1404閲覧

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

puro

総合スコア4

OCaml

OCaml(オーキャムル)は、フランスのINRIAが開発した関数型言語MLの一種で、 最新の言語理論の成果が取り入れられているプログラミング言語です。

0グッド

0クリップ

投稿2021/05/26 17:45

前提・実現したいこと

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ozwk

2021/05/27 00:00 編集

> 畳み込み関数がよくわからないので 「(出典元)でこういう説明がされているがここがわからない」というような書き方でお願いします。 さもないとそのへんに転がっている説明を焼き直すぐらいしかできません: [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) ...)) です。末尾再帰になっていません。 これを読んでどこがわからないですか?
guest

回答1

0

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

畳み込み関数について

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

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

ocaml

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

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

ocaml

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

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

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

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

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

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

ocaml

1val max_of_int_list: int list -> int

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

ocaml

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

これで完成です。

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

ocaml

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

ocaml

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

注意点

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

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

投稿2021/10/15 17:35

fj68

総合スコア752

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問