您将如何在 Haskell 中使用 foldr 定义地图和过滤器? [英] How would you define map and filter using foldr in Haskell?

问题描述

我正在对函数式语言(目前使用 Haskell)进行一些自学.我遇到了一个基于 Haskell 的赋值，它需要根据 foldr 定义映射和过滤器.对于我的一生，我并不完全理解如何去做.

I'm doing a bit of self study on functional languages (currently using Haskell). I came across a Haskell based assignment which requires defining map and filter in terms of foldr. For the life of me I'm not fully understanding how to go about this.

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

For example when I define a map function like:

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

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

I don't know why the first element of the list is always ignored. Meaning that:

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

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

results in [4,6,8] instead of [2,4,6,8]

同样，我的过滤器功能:

Similarly, my filter' function:

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]

results in [4,6] instead of [2,4,6]

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

Why would this be the case? And how SHOULD I have defined these functions to get the expected results? I'm assuming something is wrong with my lambda expressions...

推荐答案

我希望我可以发表评论，但唉，我的业力不够.

I wish I could just comment, but alas, I don't have enough karma.

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

The other answers are all good ones, but I think the biggest confusion seems to be stemming from your use of x and xs.

如果你改写为

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

你会清楚地看到 x 甚至没有在右侧提到，所以它不可能出现在解决方案中.

you would clearly see that x is not even mentioned on the right-hand side, so there's no way that it could be in the solution.

干杯

这篇关于您将如何在 Haskell 中使用 foldr 定义地图和过滤器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！