这个基于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]