我正在学习Haskell,并尝试编写自己的反转函数,但不使用递归。
这个解决方案是这个函数:
myreverse = foldl (flip (:)) []
我正在尝试理解在评估以下内容时会发生什么:
myreverse [1..5]
我不明白 flip 在这里的作用。有人能写下这里发生了什么,并逐步解释吗?
翻转函数非常简单:
如果有一个函数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]
foldl
不会导致范围从开头完全评估。 - jub0bsflip
、(:)
和foldl
的工作方式能更明显。 - Random Devflip
命令来理解它的作用::t (:)
(:) 1 [2..4]
[1,2,3,4]
:t flip (:)
(flip (:)) [2..4] 1
[1,2,3,4]
flip
是做什么的。如果你把(:)
写成 lambda 形式:\x xs -> x : xs
,可能会更有帮助。如果你将flip
应用于这个 lambda,得到的函数是\xs x -> x : xs
。 - jub0bsfoldl'
而不是foldl
。除非你正在解决一些疯狂的虚构问题,否则普通的foldl
永远不是最佳选择。 - hugomgflip(:)
不进行任何实际计算,因此我希望GHC将其视为构造函数。但是,您必须进行测试以确保。 - dfeuer