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

Question

我正在做YAHT的递归数据类型部分的练习，并发现写作listFoldr 函数有点具有挑战性（主要是因为我一开始并没有真正理解 foldl 和 foldr 之间的区别）。 当我最终意识到 foldr 函数的工作原理时，我决定只需简单交换函数参数即可将我的 listFoldl 函数更改为 < code>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

但是 为练习提供的解决方案与我的有很大不同。 他们的 listFoldl 和我的一模一样，但是看看他们的 listFoldr：

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

哪个解决方案更好，我的还是他们的？ 其中之一是错误的吗？ （在我的测试中，它们最终得到完全相同的结果......）

Answer 1

你的解决方案肯定是不正确的。 您只需实现一个 foldl，其中函数 f 以相反的顺序接受参数。 例如，错误的地方是， foldr (:) [] 应该是列表上的识别函数，但您的函数反转了列表。 还有很多其他原因导致您的函数不是 foldr，例如 foldr 如何在无限列表上工作，而您的函数则不然。 它们在您的示例中相同纯属巧合，因为 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4))。 我认为你应该从头开始，看看 foldr 应该如何工作。

Answer 2

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

您应该能够通过“顺序很重要”的示例来证明这一点。 例如，类似

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

where 'f' 是一个函数，类似于

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

where '@' 是一个字符串追加运算符（我忘记了它在 Haskell 中是什么）。 重点只是“检测”该函数，以便您可以看到使用各种参数调用它的顺序。

（请注意，这没有出现在您的示例中，因为数学“4-1-2-3”产生与“4-3-2-1”相同的答案。）

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 是非交换性和非关联性的（即，参数和应用程序顺序很重要），因此您可以确保表达式的计算正确。 当然，减法是非交换性和非结合性的，你只是运气不好。