关于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维基上有一些折叠工作的不同命令的漂亮图片:

这显示了如何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

因此,即使类型匹配,您也必须仔细考虑您的函数正在做什么.考虑折叠之类的东西可能会让人困惑一段时间,但你会习惯它.