haskell - 以下 foldl 实现有什么问题？

Question

根据任务，我们必须通过 foldr 实现 foldl。通过比较函数签名和 foldl 实现，我得到了以下解决方案:

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl _ acc [] = acc
myFoldl fn acc (x:xs) = foldr fn' (fn' x acc) xs
    where
    fn' = flip fn

只需翻转函数参数以满足 foldr 预期类型并通过递归应用传递的函数来模拟 foldl 定义。
这是一个惊喜，因为我的老师给这个答案打了零分。

我什至检查了这个定义以与标准 foldl 相同的方式堆叠其中间结果:

 > myFoldl (\a elm -> concat ["(",a,"+",elm,")"]) "" (map show [1..10])
 > "((((((((((+1)+10)+9)+8)+7)+6)+5)+4)+3)+2)"
 > foldl (\a elm -> concat ["(",a,"+",elm,")"]) "" (map show [1..10])
 > "((((((((((+1)+10)+9)+8)+7)+6)+5)+4)+3)+2)"

正确答案是以下定义:

myFoldl :: (a -> b -> a) -> a -> [b] -> a    
myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

只是问为什么我以前的定义不正确？

Answer 1

本质上，你的弃牌顺序错误。我认为您没有从 foldl 复制您的输出正确；我得到以下信息:

*Main> myFoldl (\ a elem -> concat ["(", a, "+", elem, ")"]) "" (map show [1..10])
"((((((((((+1)+10)+9)+8)+7)+6)+5)+4)+3)+2)"
*Main> foldl (\ a elem -> concat ["(", a, "+", elem, ")"]) "" (map show [1..10])
"((((((((((+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)"

所以会发生什么是您的实现获得第一个元素 - 基本情况 - 正确但然后使用 foldr 其余的导致其他所有内容都向后处理。

在 Haskell wiki 上有一些很好的图片，展示了折叠的不同顺序。 :





这显示了 foldr (:) []应该是列表的标识和 foldl (flip (:)) []应该反转一个列表。在您的情况下，它所做的只是将第一个元素放在最后，但其他所有元素都保持相同的顺序。这正是我的意思:

*Main> foldl (flip (:)) [] [1..10]
[10,9,8,7,6,5,4,3,2,1]
*Main> myFoldl (flip (:)) [] [1..10]
[2,3,4,5,6,7,8,9,10,1]

这将我们带到了一个更深、更重要的点——即使在 Haskell 中，仅仅因为类型排列并不意味着您的代码可以工作。 Haskell 类型系统不是万能的，通常有很多——甚至是无限数量的——满足任何给定类型的函数。作为一个退化的例子，即使是以下 myFoldl 的定义类型检查:

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl _ acc _ = acc

因此，即使类型匹配，您也必须准确考虑您的函数在做什么。考虑像折叠这样的事情可能会让人困惑一段时间，但你会习惯的。