这是写的Haskell foldr相似功能的正确方法是什么？

Question

我正在做从 YAHT的递归数据类型部分，发现写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

此出现工作（I做比这更多的测试）：

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)

哪些溶液是较好的，矿山或他们的？就是其中的一个不正确的？ （在我的测试，它们都结束了完全相同的结果...）

Answer 1

我想你正在处理在“相反的顺序”的元素，所以你的是不正确的。

您应该能够用一个例子，其中“顺序事项”来证明这一点。例如，像

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

其中，“F”是沿

的线的功能

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

其中“@”是一个字符串追加操作符（I忘记它是什么在Haskell）。问题的关键是只是“仪器”的功能，所以你可以看到什么样的顺序是越来越调用各种ARGS。

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

Answer 2

您的解决方案是绝对不正确。您只是实现了一个foldl其中功能f接受参数按相反的顺序。例如，什么是错的，foldr (:) []应该是名单上的识别功能，但你的函数反转列表。还有很多其他的原因使您的功能不foldr，像foldr如何作用于无限的名单和你没有。这是一个巧合，他们是在你的例子一样，因为3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4))。我想你应该从头开始，并期待在foldr是如何工作的。

Answer 3

此致被打破。的东西不与单个数字结果最终尝试。

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

您正在处理在错误的方向。

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即非交换和非缔合（即，参数，并应用顺序物质）来传递，所以可以肯定的表达被正确地评估。当然，减法非交换和非关联和你刚不走运。