你如何在Haskell中使用foldr定义地图和过滤器？

Question

我正在做一些关于函数式语言的自学(目前正在使用Haskell).我遇到了一个基于Haskell的任务,需要根据foldr定义地图和过滤器.对于我的生活,我不完全理解如何去做.

例如,当我定义一个地图函数时:

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

我不知道为什么列表的第一个元素总是被忽略.意思是:

map' (*2) [1,2,3,4]

得出[4,6,8]而不是[2,4,6,8]

同样,我的过滤器功能:

filter'             :: (a -> Bool) -> [a] -> [a]
filter' p []        = []
filter' p (x:xs)    = foldr (\x xs -> if p x then x:xs else xs ) [] xs

当运行时:

filter' even [2,3,4,5,6]

结果为[4,6]而不是[2,4,6]

为什么会这样呢？我应该如何定义这些函数以获得预期的结果？我假设我的lambda表达式有问题......

Answer 1

我希望我能发表评论,但唉,我没有足够的业力.

其他答案都很好,但我认为最大的困惑似乎源于你使用x和xs.

如果你把它重写为

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f (x:xs)   = foldr (\y ys -> (f y):ys) [] xs

你会清楚地看到x在右侧甚至没有提到,因此它无法在解决方案中出现.

干杯

Answer 2

对于您的第一个问题,foldr已经有空列表的情况,因此您不需要也不应该在自己的地图中提供案例.

map' f = foldr (\x xs -> f x : xs) []

这同样适用 filter'

filter' p = foldr (\x xs -> if p x then x : xs else xs) []

你的lambda表达式没有任何问题,但你对filter'和的定义有问题map'.在缺点情况下(x:xs)你吃头(x)然后将尾巴传递给foldr.该foldr函数永远不会看到您已经吃过的第一个元素.:)

另请注意:

filter' p = foldr (\x xs -> if p x then x : xs else xs) []

是等价的(η-等价):

filter' p xs = foldr (\x xs -> if p x then x : xs else xs) [] xs

Answer 3

我将使用 foldr 和函数组合定义地图，如下所示：

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

对于过滤器的情况：

filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr (\x xs -> if p x then x:xs else xs) []

请注意，使用 foldr 或 foldl 在列表上定义函数时，不必传递列表本身。您的解决方案的问题是您删除了列表的头部，然后将地图应用于列表，这就是为什么在显示结果时列表的头部丢失的原因。