haskell - 这个基于 foldl 的函数是如何工作的 : "myreverse = foldl (flip (:)) []"?

Question

我正在学习haskell，并且尝试在不使用递归的情况下编写自己的反向函数。

解决方案是这个函数:

myreverse = foldl (flip (:)) []

我试图了解在评估过程中会发生什么，比如:

myreverse [1..5]

我不明白翻转在这里做什么。有人可以用分步说明写下这里发生的事情吗？

Answer 1

翻转相当容易:

如果您有函数 f :: a -> b -> c然后 flip f是一个函数 :: b -> a -> c所以它给你一个新函数和 翻转 您必须传递的参数顺序。
(:) :: a -> [a] -> [a]是这种模式的函数，所以 flip (:)现在将是一个函数，它首先获取即将成为的尾部，然后是新的头部，并返回一个包含以下内容的新列表:

(flip (:)) [2..4] 1
= (:) 1 [2..4]
= 1 : [2..4]
= [1,2,3,4]

现在你需要这个，因为 foldl是这样定义的:

foldl :: (b -> a -> b) -> b -> [a] -> b

你看 - 你必须传递的函数在这里是一个首先接受一个列表然后一个元素并返回一个新列表的函数

这现在将全部折叠成这样的东西:

myreverse [1..5]
= foldl (flip (:)) [] [1,2,3,4,5]
= foldl (flip (:)) (((flip (:)) [] 1)) [2,3,4,5]
= foldl (flip (:)) (1:[]) [2,3,4,5]
= foldl (flip (:)) (((flip (:)) [1] 2)) [3,4,5]
= foldl (flip (:)) (2:[1]) [3,4,5]
= ...
= [5,4,3,2,1]