1

私はYAHT の再帰的データ型セクションの演習を行っていましたが、関数を書くのが少し難しいことに気付きました (主な理由は、最初はとlistFoldrの違いがよくわからなかったからです)。関数がどのように機能するかを最終的に正確に理解したとき、関数を関数に変更するために必要なのは関数の引数の単純な交換だけであると判断しました。foldlfoldrfoldrlistFoldllistFoldr

listFoldl f i [] = i
listFoldl f i (x:xs) = listFoldl f (f i x) xs

listFoldr f i [] = i
listFoldr f i (x:xs) = listFoldr f (f x i) xs

これは機能しているようです（これよりも多くのテストを行いました）：

Main> foldr (-) 4 [1, 2, 3]
-2
Main> listFoldr (-) 4 [1, 2, 3]
-2

しかし、演習に与えられた解決策は、私のものとは大きく異なります。それらlistFoldlは私のものとまったく同じですが、それらを見てくださいlistFoldr：

listFoldr f i [] = i
listFoldr f i (x:xs) = f x (listFoldr f i xs)

私のソリューションと彼らのソリューションのどちらが優れていますか? それらの1つは間違っていますか？（私のテストでは、どちらもまったく同じ結果になります...）

4

4 に答える 4

5

あなたの解決策は間違いなく間違っています。foldl関数fが逆の順序で引数を取るaを実装しただけです。たとえば、何が悪いのかというと、foldr (:) []リストの恒等関数であるはずですが、関数はリストを逆にします。関数が機能しない理由は他にもたくさんあります。たとえば、無限のリストでfoldrどのように機能するのか、そうでないのかなどです。foldrあなたの例でそれらが同じであるのはまったくの偶然です。なぜなら3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4))。ゼロから始めて、どのように機能するかを確認する必要があると思いますfoldr。

于 2009-05-16T05:35:28.950 に答える
4

「逆の順序」で要素を処理していると思うので、あなたのは正しくありません。

「順序が重要」な例でこれを実証できるはずです。たとえば、次のようなもの

listfoldr f "" ["a", "b", "c"]

ここで、「f」は次の行に沿った関数です

f s1 s2 = "now processing f(" @ s1 @ "," @ s2 @ ")\n"

ここで、「@」は文字列追加演算子です (Haskell での意味は忘れました)。ポイントは、関数を「計測」して、さまざまな引数で呼び出される順序を確認できるようにすることです。

(数学「4-1-2-3」は「4-3-2-1」と同じ答えをもたらすため、これはあなたの例には表示されないことに注意してください。)

于 2009-05-16T05:21:11.637 に答える
4

あなたのものは壊れています。単一の数値結果に終わらないもので試してください。

eg: listFoldr (++) "a" ["b", "c", "d"]

間違った方向に処理しています。

于 2009-05-16T05:27:05.307 に答える
2

リスト[x1, x2, ..., xk]で、あなたのlistFoldr計算

 f xk (... (f x2 (f x1 i)) ...)

一方、foldr計算する必要があります

 f x1 (f x2 (... (f xk i) ...))

(比較foldlすると、

f (... (f (f i x1) x2) ...) xk

基本的に、listFoldr f = foldl (flip f).)

あなたのテストケースは残念です。

3 - (2 - (1 - 4)) = 1 - (2  - (3 - 4))

このような関数をテストするときはf、式が正しく評価されることを確認できるように、可換性と結合性がない (つまり、引数とアプリケーションの順序が重要である) を渡すようにしてください。もちろん、引き算は可換性も結合性もありません。運が悪かっただけです。

于 2009-05-16T14:39:27.240 に答える