这是编写Haskell foldr函数的正确方法吗？

Question

我在做YAHT's Recursive Datatype这个练习部分，发现编写listFoldr函数有点难度（主要是因为我起初并没有真正理解foldl和foldr之间的区别）。当我终于实现完全foldr功能是如何工作的，我决定函数参数的简单交换是一切会需要我listFoldl功能更改为listFoldr功能：

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) 

哪种方案更好的，我的还是他们？他们中的一个是不正确的？ （在我的测试中，他们最终都得到了完全相同的结果......）

Answer 1

我认为你正在处理'相反顺序'中的元素，所以你的是不正确的。

你应该能够用'订单重要'的例子来证明这一点。例如，像

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

，其中“F”是沿

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

其中“@”是一个字符串追加运营商线路的功能（我忘了这是在Haskell）。重点在于'仪器'的功能，所以你可以看到它与各种参数调用的顺序。

（请注意，这并不在你的例子显示出来，因为数学“4-1-2-3”得到相同的答案为“4-3-2-1”。）

Answer 2

你的是破碎。尝试一些最终不会带有单个数字结果的东西。

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

您正在处理错误的方向。

Answer 3

您的解决方案绝对不正确。您只需实现一个foldl，其中函数f以相反的顺序参数。例如，什么是错误的，foldr (:) []应该是列表上的标识函数，但是你的函数会颠倒列表。有很多其他原因，为什么你的功能不是foldr，就像foldr如何在无限列表上工作，而你的功能不是。这是一个纯粹的巧合，他们在你的例子是相同的，因为3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4))。我认为你应该从头开始，看看foldr应该如何工作。

Answer 4

在列表[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即非交换和非关联（即，参数和应用传递顺序问题），所以你可以确定表达式被正确评估。当然，减法是不可交换和非关联的，你只是不幸。