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

问题描述

我正在做功能语言的自学（目前使用Haskell）。我遇到了一个基于Haskell的作业，需要根据foldr定义地图和过滤器。对于我的生活，我并没有完全理解这一点。

例如，当我定义一个地图函数，如：

  map'::（a  - > b） - > [a]  - > [b] 
 map'f [] = [] 
 map'f（x：xs）= foldr（\x xs  - >（fx）：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 px then x：xs else xs）[] xs 
  

当运行为：

 过滤器[2,3,4,5,6] 
  

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

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

解决方案

我希望我只能评论，但唉，我没有足够的业力。

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

如果您将其重写为

  map'::（a - > b）→> [a]  - > [b] 
 map'f [] = [] 
 map'f（x：xs）= foldr（\y ys  - >（fy）：ys）[] xs 
  

你会清楚地看到 x 在右边，所以没有办法可以在解决方案。

干杯

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]

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

when run as:

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

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

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.

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

If you rewrote it as

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

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.

Cheers

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