您如何在Haskell中使用文件夹定义地图和过滤器?

| 我正在对功能语言进行一些自学(目前正在使用Haskell)。我遇到了一个基于Haskell的作业,该作业需要根据文件夹定义地图和过滤器。对于我的一生,我还没有完全理解如何去做。 例如,当我定义一个地图函数时:
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'函数:
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表达式有问题...
已邀请:
我希望我可以发表评论,但是,我没有足够的业力。 其他答案都是好的答案,但我认为最大的困惑似乎是您使用x和xs造成的。 如果您改写为
map\'            :: (a -> b) -> [a] -> [b]
map\' f []       = []
map\' f (x:xs)   = foldr (\\y ys -> (f y):ys) [] xs
您会清楚地看到在右侧甚至没有提到
x
,因此解决方案中不可能存在它。 干杯
对于第一个问题,ѭ6已经有一个空列表用例,因此您不需要,也不应该在自己的地图中提供一个用例。
map\' f = foldr (\\x xs -> f x : xs) []
filter\'
也一样
filter\' p = foldr (\\x xs -> if p x then x : xs else xs) []
lambda表达式没什么问题,但是but8ѭ和
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
我将使用文件夹和函数组成来定义地图,如下所示:
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在列表上定义函数时,不必传递列表本身。 解决方案的问题是,您放下列表的标题,然后将地图应用于列表,然后 这就是为什么在显示结果时缺少列表标题的原因。
在定义中,您正在对pattern19ѭ进行模式匹配,这意味着,当参数为
[1,2,3,4]
时,
x
绑定到
1
,而
xs
绑定到列表的其余部分:
[2,3,4]
。 您不应该做的只是丢掉25英镑的部分。这样,您的
foldr
就会在整个列表中起作用。 因此,您的定义应如下所示:
map\'            :: (a -> b) -> [a] -> [b]
map\' f []       = []
map\' f xs       = foldr (\\x xs -> (f x):xs) [] xs
filter\'             :: (a -> Bool) -> [a] -> [a]
filter\' p []        = []
filter\' p xs        = foldr (\\x xs -> if p x then x:xs else xs ) [] xs
我是Haskell的新手(实际上,我已经找到此页面询问相同的问题),但这是到目前为止我对列表和文件夹的理解: 列表是使用cons
(:)
运算符链接到下一个元素的元素。它们以空列表
[]
结尾。 (像加法运算符
(+)
1+2+3+4 = 10
1:2:3:4:[] = [1,2,3,4]
foldr函数采用一个带有两个参数的函数。这将替换cons运算符,后者将定义每个项目如何链接到下一个项目。 它还需要操作的最终值,该值可能很难作为将分配给空列表的初始值。对于缺点,它是空列表
[]
。如果将空列表链接到任何列表,则结果是列表本身。因此对于
sum
函数,它是
0
。对于乘法函数,它是
1
,依此类推。 它需要列表本身 所以我的解决方案如下:
filter\' p = foldr (\\x n -> if p x then x : n else n) []
lambda表达式是我们的链接函数,它将代替cons
(:)
运算符使用。空列表是空列表的默认值。如果满足谓词条件,则照常使用
(:)
链接到下一个项目,否则我们根本不链接。
map\' f = foldr (\\x n -> f x : n) []
在这里,我们将
f x
链接到下一个项目,而不仅仅是
x
,它只是复制列表。 另外,请注意,您不需要使用模式匹配,因为我们已经告诉foldr列表为空时该怎么做。 我知道这个问题确实很老,但无论如何我都想回答。我希望这不违反规则。
考虑它的另一种方式-文件夹存在,因为经常使用以下递归模式:
-- Example 1: Sum up numbers
summa :: Num a => [a] -> a
summa []     = 0
summa (x:xs) = x + suma xs
在结构上取数字甚至取反,在结构上看起来与以前的递归函数非常相似:
-- Example 2: Reverse numbers
reverso :: [a] -> [a]
reverso []      = []
reverso (x:xs)  = x `op` reverso xs
  where
    op = (\\curr acc -> acc ++ [curr])
上面示例中的结构仅在初始值(求和为
0
,反向为
[]
)以及运算符之间在第一值和递归调用之间有所不同(求和为
+
,反向为
(\\q qs -> qs ++ [q])
)。因此,以上示例的功能结构通常可以看作是
-- Generic function structure
foo :: (a -> [a] -> [a]) -> [a] -> [a] -> [a]
foo op init_val []      = init_val
foo op init_val (x:xs)  = x `op` foo op init_val xs
要查看此“通用” foo的工作原理,我们现在可以使用foo并将其传递给运算符,初始值和列表本身来重写reverso:
-- Test: reverso using foo
foo (\\curr acc -> acc ++ [curr]) [] [1,2,3,4]
让我们给foo一个更通用的类型签名,以便它也可以解决其他问题:
foo :: (a -> b -> b) -> b -> [a] -> b
现在,回到您的问题-我们可以这样编写过滤器:
-- Example 3: filter
filtero :: (a -> Bool) -> [a] -> [a]
filtero p []     = []
filtero p (x:xs) = x `filterLogic` (filtero p xs)
  where
     filterLogic = (\\curr acc -> if (p curr) then curr:acc else acc)
这又具有与求和和逆转非常相似的结构。因此,我们应该能够使用foo重写它。假设我们要从列表[1,2,3,4]中过滤偶数。然后,我们再次将运算符foo(在本例中为
filterLogic
),初始值和列表本身传递给foo。在此示例中,ѭ54takes具有一个称为谓词的
p
函数,我们必须为该调用定义该函数:
let p = even in foo (\\curr acc -> if (p curr) then curr:acc else acc) [] [1,2,3,4] 
Haskell中的foo称为文件夹。因此,我们已经使用文件夹重写了过滤器。
let p = even in foldr (\\curr acc -> if (p curr) then curr:acc else acc) [] [1,2,3,4] 
因此,可以使用foldr编写过滤器,如下所示:
-- Solution 1: filter using foldr
filtero\' :: (a -> Bool) -> [a] -> [a]
filtero\' p xs = foldr (\\curr acc -> if (p curr) then curr:acc else acc) [] xs 
至于地图,我们也可以写成
-- Example 4: map
mapo :: (a -> b) -> [a] -> [b]
mapo f []   = []
mapo f (x:xs) = x `op` (mapo f xs)
  where
    op = (\\curr acc -> (f curr) : acc)
因此,可以使用文件夹将其重写。例如,将列表中的每个数字乘以2:
let f = (* 2) in foldr (\\curr acc -> (f curr) : acc) [] [1,2,3,4]
因此,我们可以使用foldr编写地图,如下所示:
-- Solution 2: map using foldr
mapo\' :: (a -> b) -> [a] -> [b]
mapo\' f xs = foldr (\\curr acc -> (f curr) : acc) [] xs
您的解决方案几乎可以使用。) 问题在于您在两个函数中(在patternmatching内部和在lambda表达式内部)都具有两个x的differend绑定,因此您无法跟踪第一个Element。
map\'            :: (a -> b) -> [a] -> [b]
map\' f []       = []
map\' f (x:xs)   = foldr (\\x xs -> (f x):xs) [] (x:xs)

filter\'             :: (a -> Bool) -> [a] -> [a]
filter\' p []        = []
filter\' p (x:xs)    = foldr (\\x xs -> if p x then x:xs else xs ) [] (x:xs)
这应该是把戏:)。另外:您可以轻松编写无点样式的函数。

要回复问题请先登录注册