4

関数型プログラミングに関する大学のコースがあり、SMLを使用しています。試験の準備として、私は解決策のない古い試験セットのいくつかに取り組んでいます。

私が本当に問題を抱えている唯一の質問の1つは、次の質問を使用していfoldlます。

プログラムのスケルトンについて考えてみましょう。funaddGtkxs = List.foldl（...）... xs; addGt k xsがxs内の要素の合計であり、kより大きいように、2つの欠落している部分（ドットで表されます...）を入力します。たとえば、addGt 4 [1、5、2、7、4、8] = 5 + 7 + 8 = 20

これは本当に簡単なことだと思いますが、foldlとfoldrの機能を理解するのは非常に困難です。

私が今持っているのは次のとおりです（私のコンパイラに聞いたら、これは非常に間違っているようです！）：

fun addGt(k,xs) = List.foldl ( fn x => if x > k then op+ else 0) 0 xs;

この質問について助けていただければ幸いです。またfoldl、foldr機能に光を当てる非常に短いコメントかもしれません。

4

2 に答える 2

9

私が考えた解決策は次のとおりです。

fun addGt(k, xs) = List.foldl (fn (x, y) => if x >= 5  then x + y else y) 0 xs;

しかし、説明させてください。まず、List.foldl関数の型を確認します。それは次のとおりです。

('a * 'b -> 'b) -> 'b -> 'a list -> 'b

タイプ の別の関数を最初のパラメーターとして受け取るカリー化されList.foldlた関数も同様です。type を持つものを使用しました。代わりに、タイプのタプルを取り、を返す関数を提供する必要があるため、次のようになります。コードがコンパイルされなかったのはそのためです。間違ったタイプの関数を.('a * 'b -> 'b)(fn x => if x > k then op+ else 0)int -> intList.foldlint * intint(fn (x, y) => do stuff)foldl

foldlこれで、次のように考えることができます。

foldl f b [x_1, x_2, ..., x_(n - 1), x_n] = f(x_n, f(x_(n - 1), ..., f(x2, f(x1, b)) ...))ここfで、 は type の関数であり('a * 'b -> 'b)、bは type のもので'bあり、リスト[x_1, x_2, ..., x_(n - 1), x_n]は type'a listです。

同様に、次のfoldrように考えることができます。

foldr f b [x_1, x_2, ..., x_(n - 1), x_n] = f(x_1, f(x_2, ..., f(x_(n - 1), f(x_ n, b))

于 2011-05-11T11:19:26.007 に答える
2

foldl f s lsリストを呼び出すとls = [x1, x2, ..., xn]、次の結果が得られます。

f(xn, ... f(x2, f(x1, s)))

つまり、見つけることから始まります。

a1 = f(x1, s)

それで

a2 = f(x2, a1)

など、リストを通過するまで。

完了すると、 が返されますan。

a-values は一種のaccumulatorであると考えることができます。aiつまり、リストが唯一[x1, x2, ..., xi](または、リストの最初の i 要素) である場合の結果です。

関数は通常、次の形式になります。

fn (x, a) => ...

次に行う必要があるのは、次のことを考えることです: リスト内に次の要素 と、 listの結果であるx(i+1)valueがある場合、次の結果であるvalue を見つけるために何をする必要がありますか?リスト。ai[x1, x2, ..., xi]a(i+1)[x1, x2, ..., xi, x(i+1)]

s空のリストに与えられた値と考えることができます。

foldrは同じように機能しますが、リストの先頭ではなく末尾から開始するだけです。

于 2011-05-11T11:27:27.887 に答える