ghc - 使用 foldl', foldr 列出连接

Question

我现在正在学习 Haskell，但面临以下问题:

我想使用 foldl' 和 foldr 重写++ 函数。我已经用 foldr 完成了:

myConcat xs ys = foldr (:) ys xs

我不能使用 foldl' 来做到这一点。我读过 RealWorldHaskell该 foldr 对于做这种事情很有用。
好的，但我不能也用 foldl 写一个等价于++ 的东西吗？有人可以告诉我如何做到这一点(如果可以做到的话......这本书没有提到任何关于它的内容)......

Haskell 的类型机制是否阻止我这样做？每次我尝试时，我都会遇到类型错误...

Answer 1

我猜你得到的错误是试图简单地切换 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。