這是編寫Haskell foldr函數的正確方法嗎？

我在做YAHT's Recursive Datatype這個練習部分，發現編寫listFoldr函數有點難度（主要是因爲我起初並沒有真正理解foldl和foldr之間的區別）。當我終於實現完全foldr功能是如何工作的，我決定函數參數的簡單交換是一切會需要我listFoldl功能更改爲listFoldr功能：這是編寫Haskell 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

這似乎工作（我沒有比這更多的測試）：

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)

哪種方案更好的，我的還是他們？他們中的一個是不正確的？（在我的測試中，他們最終都得到了完全相同的結果......）

來源

2009-05-16 Jeremy Ruten

我認爲你正在處理'相反順序'中的元素，所以你的是不正確的。

你應該能夠用'訂單重要'的例子來證明這一點。例如，像

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-16 05:21:11 Brian

啊我想我選擇了一種不好的測試方式。謝謝！ – 2009-05-16 05:32:16

一個簡單的測試就是'listFoldr（:)「」「abc」'（如newacct提到的，'listFoldr（:) []'是列表的標識函數） – 2012-10-14 16:19:43

你的是破碎。嘗試一些最終不會帶有單個數字結果的東西。

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

您正在處理錯誤的方向。

來源

2009-05-16 05:27:05

您的解決方案絕對不正確。您只需實現一個foldl，其中函數f以相反的順序參數。例如，什麼是錯誤的，foldr (:) []應該是列表上的標識函數，但是你的函數會顛倒列表。有很多其他原因，爲什麼你的功能不是foldr，就像foldr如何在無限列表上工作，而你的功能不是。這是一個純粹的巧合，他們在你的例子是相同的，因爲3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4))。我認爲你應該從頭開始，看看foldr應該如何工作。

來源

2009-05-16 05:35:28 newacct

在列表[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-16 14:39:27

這是編寫Haskell foldr函數的正確方法嗎？

回答

相關問題