これは、Haskell foldr関数を記述する正しい方法ですか？

Question

私はYAHT's Recursive Datatypeセクションから練習をしていましたが、listFoldr関数を書くのはちょっと難しいです（主にfoldlとfoldrの違いを最初に理解していなかったからです）。 （

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 

これは動作するように表示されます。私は最終的にfoldr機能が働いていた方法を正確に気づいたとき、私は、関数の引数のシンプルスワップはそれがlistFoldr関数に私のlistFoldl機能を変更するために必要なことと思いますすべてのだろうと決めました私が）これ以上のテストをしました：

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

しかし、運動のために与えられたsolutionは私よりもはるかに異なっています。彼らのlistFoldlは私と全く同じであるが、そのlistFoldrを見て：

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

良く、鉱山または彼らはどれソリューション？そのうちの1つは間違っていますか？ （私のテストでは、両者はまったく同じ結果に終わります...）

Answer 1

「反対の順序」で要素を処理していると思います。

「発注事項」の例でこれを実証できるはずです。たとえば、「F」が「@」文字列追記演算子である

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

の線に沿って機能です

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

のようなものは、（私はそれがHaskellであるものを忘れて）。ポイントは、関数を '計測'することにすぎないので、さまざまな引数でどのような順序で呼び出されているのかを確認できます。

（「4-3-2-1」と同じ答えを生み出す「4-1-2-3」数学ので、これはあなたの例では現れなかったことに注意してください。）

Answer 2

ユアーズされます壊れた。単一の数値結果で終わらないもので試してみてください。

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

不適切な方向に処理しています。

Answer 3

解決策は間違いありません。 fが逆の順序で引数を取るfoldlを実装しました。何が間違っているかなど、foldr (:) []はリストの識別関数であると考えられますが、関数はリストを逆にします。あなたの機能がfoldrでない理由は他にもたくさんあります。例えば、foldrは無限のリストで動作し、あなたのものはそうではありません。 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4))があなたの例で同じであることは、純粋な偶然の一致です。 foldrの仕組みを見て、最初からやり直すべきだと思います。リスト[x1, x2, ..., xk]で

Answer 4

foldrが

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

を計算しなければならないのに対し、あなたのlistFoldrは

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

を計算（比較では、foldlは、基本的に

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

、listFoldr f = foldl (flip f)を計算します。）あなたはこれらのような機能をテストしている場合は、非可換と非会合（すなわち、引数およびアプリケーションですfに渡すようにしてください

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

ので

あなたしているテストケースは、残念なことです注文事項）、式が正しく評価されているかどうかを確認することができます。もちろん、減算は非可換で非結合であり、あなたは不運になります。