我现在正在学习Haskell,我遇到了以下问题:
我想用foldl'和foldr重写++函数.我用foldr完成了它:
myConcat xs ys = foldr (:) ys xs
我不能用foldl'来做.我在RealWorldHaskell中读过,foldr对于做这种事情非常有用.好的,但是我不能用foldl写一个等价的++？有人可以告诉我如何做到这一点(如果可以做到......这本书没有提到任何关于它的事情)......
Haskell的类型机制阻止我这样做吗？每次我尝试我都会遇到类型错误...
该:运算符连接一个单一的元素,它的左参数,到一个列表,它右边的参数.
参数foldl是,
回想一下,折叠函数作为其左参数采用当前值,该值以初始值开始.因此,折叠函数的左参数是一个列表,其右参数是单个值.如果你玩它,你可以得到像[通过切换参数使类型匹配],
> foldl (\x y -> y:x) [1, 2, 3] [4, 5, 6]
[6,5,4,1,2,3]
但是,这不是你想要的.你必须自己解决; 我能够构建一个反向函数foldl并将其作为子例程调用 - 但如果可以的话,可以随意解决它.
我猜你得到的错误是试图简单地切换foldr到foldl':
myConcat xs ys = foldl' (:) ys xs
产生错误(使用我的Hugs REPL):
ERROR - Type error in application
*** Expression : foldl' (:) xs ys
*** Term : (:)
*** Type : a -> [a] -> [a]
*** Does not match : [a] -> a -> [a]
请注意最后两行(提供的类型和预期类型)中位置[a]和a位置相反的位置.这意味着我们需要一个类似的函数(:),但它以相反的顺序获取它的参数.
Haskell有一个为我们做这个flip功能的功能:功能.基本上,flip相当于
flip :: (a -> b -> c) -> (b -> a -> c)
flip f y x = f x y
也就是说,flip将二进制函数作为参数,并返回另一个二进制函数,其参数与原始参数相反("翻转").因此,虽然(:)有类型a -> [a] -> [a],但我们看到它flip (:)具有类型[a] -> a -> [a],使其成为一个完美的候选参数foldl'.
使用flip,我们现在有这个代码:
myConcat xs ys = foldl' (flip (:)) ys xs
这个结果来自于foldl'具有类型的事实(a -> b -> c) -> a -> [b] -> c
带参数运行这个[1..5]和[6..10],我们得到的结果[5,4,3,2,1,6,7,8,9,10],这是我们想要什么差不多.唯一的问题是第一个列表在结果中向后转.添加一个简单的调用reverse给我们最终的定义myConcat:
myConcat xs ys = foldl' (flip (:)) ys (reverse xs)
纵观这一过程中显示的编写Haskell代码时经常出现的好东西之一:当你遇到问题,你可以解决它一次一个(小)的步骤.当你已经有一个有效的实现时,尤其如此,你只是想写另一个.要注意的一件大事是,如果你改变了执行的一个部分(在这种情况下,改变foldr到foldl'),那么许多其他需要改变简单地掉出类型定义的.剩下的少数是纠正问题,可以通过运行测试用例或查看所用函数的确切性质来轻松找到.
PS:任何能够梳理最后一行代码的Haskell人都可以自由地这样做.虽然它并不可怕,但我觉得它不是很漂亮.不幸的是,我对Haskell还不是很好.