使用foldr在Haskell中定义地图,

Question

我是Haskell的新手并尝试理解地图功能.

到目前为止,我理解以下内容.

map::(a->b)->[a]->[b]
map f (x:xs) = f x : map f xs

但我不明白以下定义:使用foldr定义地图

map'::(a->b)->[a]->[b]
map' f = foldr ( (:).f ) []

任何人都可以解释上面的地图'定义以及为什么它与地图相同

Answer 1

让我们来看看来源foldr:

foldr k z = go where
    go []     = z
    go (x:xs) = k x (go xs)

现在让我们map将定义与go上面的定义进行比较:

map f []     = []
map f (x:xs) = f x : map f xs

它看起来很相似,不是吗？让我们重写第二个子句来拉出x与递归调用结果相结合的部分:

map f []     = []
map f (x:xs) = (\v vs -> f v : vs) x (map f xs)

现在平行非常明确; 我们甚至可以写一些名字来结晶并行:

map f []     = z              where z = []
map f (x:xs) = k x (map f xs) where k = \v vs -> f v : vs

只需替换上面go所见的任何地方map f,您就会看到定义完全相同!因此,根据DRY的精神,我们可以尝试重复使用foldr以上内容:

map f = foldr (\v vs -> f v : vs) []

这让你如何从获得大的想法map来foldr.一直到你给出的定义只是一些语法技巧.我们将专注于函数参数foldr:

\v vs -> f v : vs
= { writing the infix operator prefix instead }
\v vs -> (:) (f v) vs
= { eta reduction }
\v -> (:) (f v)
= { definition of function composition }
\v -> ((:) . f) v
= { eta reduction }
(:) . f

因此,使用这种推理链,我们可以达到最终形式

map f = foldr ((:) . f) []