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

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