1

我在YAHT 的 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

但是为练习给出的解决方案与我的大不相同。他们listFoldl和我的完全一样，但是看看他们的listFoldr：

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

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

4

4 回答 4

5

您的解决方案绝对不正确。您已经简单地实现了 a foldl，其中函数f以相反的顺序接受参数。例如，什么是错误的，foldr (:) []应该是列表上的识别函数，但您的函数反转列表。您的函数 not 的原因还有很多foldr，例如foldr在无限列表上的工作方式而您的不工作。在您的示例中它们相同纯属巧合，因为3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4)). 我认为你应该从头开始，看看foldr应该如何工作。

于 2009-05-16T05:35:28.950 回答
4

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

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

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-16T05:21:11.637 回答
4

你的坏了。尝试使用不会以单个数字结果结尾的东西。

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

你正在处理错误的方向。

于 2009-05-16T05:27:05.307 回答
2

在列表中[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-16T14:39:27.240 回答