Haskell-使用foldr编写映射函数

Question

我正在尝试使用foldr编写map函数.问题是,当我运行此代码时:

> myMap f xs = foldr (\ acc x -> acc :(f x)) [] xs

我有以下问题:

使用'it'时没有(Num [a0])的实例

但是当我跑

myMap f xs = foldr (\x acc-> (f x):acc) [] xs

它完美地运作.有什么想法吗？

Answer 1

您发布的错误并非来自您的定义myMap,而是来自您使用它的方式.类型的第一个myMap是([a] -> [a]) -> [a] -> [a],不匹配的类型Prelude.map.在第二个中,您已经交换了变量名称以及您正在申请的变量名称f.编译器不关心你传递给lambda的参数的名称foldr,所以它foldr (\x acc -> f x : acc)是相同的foldr (\foo bar -> f foo : bar).这可能是你在这里绊倒的原因.

第二个是有效的,因为(简单地说)它是正确的.在第一个你正在应用f你的累加器列表x(即使你有一个名为acc它不是你的累加器的变量),所以f必须采取一个列表并返回一个列表.在第二个中,您将应用于f每个元素,然后将其添加到累加器列表中.如果你有myMap (+1),它会有类型

myMap (+1) :: Num [a] => [a] -> [a]

其中说你必须传递一个值列表,[a]其中包含[a]实现Num,当前没有实例Num [a],也没有实例.

TL; DR:在第一个中,您将映射函数应用于累加器列表,在第二个中,您将映射函数应用于每个元素.

Answer 2

折叠的类型是

foldr :: (a -> b -> b) -> b -> [a] -> b

因此,foldr用于遍历和累积列表的二进制操作具有类型(a -> b -> b),它首先取一个列表元素(类型a),然后取累加器(类型b),得到类型为b的表达式.

所以,你的第一个myMap函数不起作用,因为你正在以相反的顺序使用"acc"和"x".您想要应用于fx然后将其附加到类型的acummulator b(在这种情况下为列表)