使用Haskell的map函数计算列表的总和

Question

哈斯克尔

addm::[Int]->Int
addm (x:xs) = sum(x:xs)

我能够实现使用sum函数获得列表的总和但是可以使用函数获得列表的总和map吗？还有什么地图功能的使用？

Answer 1

您无法真正使用map总结列表,因为map会独立于其他列表元素处理每个列表元素.map例如,您可以使用增量列表中的每个值

map (+1) [1,2,3,4] -- gives [2,3,4,5]

实现addm的另一种方法是使用foldl:

addm' = foldl (+) 0

Answer 2

这是,对所谓不可能的定义sum来讲map:

sum' xs  =  let { ys = 0 : map (\(a,b) -> a + b) (zip xs ys) } in last ys

这实际上说明了如何scanl实现map,以上等同于zip:

scanl' f z xs  =  let { ys = z : map (uncurry f) (zip ys xs) } in ys

我希望可以计算很多东西last,安排各种信息流.

编辑:上面只是一个 foldl (+) 0 xs === last $ scanl (+) 0 xs伪装当然(并且map是一种zip):

sum' xs  =  let { ys = 0 : zipWith (+) ys xs } in last ys

这似乎表明,至少从这个角度来看,这zipWith是更基本的zipWith.

Answer 3

无法使用map将列表减少到其总和.那个递归模式是一个fold.

sum :: [Int] -> Int
sum = foldr (+) 0

另外,请注意您也可以定义map为折叠:

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

这是因为foldr列表上的规范递归函数.

参考文献:关于折叠的普遍性和表现力的教程,Graham Hutton,J.Functional Programming 9(4):355 - 343,1999年7月.

Answer 4

在获得一些见解之后，我必须添加另一个答案：您无法使用 获得列表的总和map，但您可以使用其 monadic 版本获得总和mapM。所有你需要做的就是用一个Writer单子（见LYAHFGG）在Sum半群（见LYAHFGG）。

我写了一个专门的版本，可能更容易理解：

data Adder a = Adder a Int

instance Monad Adder where
  return x = Adder x 0
  (Adder x s) >>= f = let Adder x' s' = f x
                      in Adder x' (s + s') 

toAdder x = Adder x x

sum' xs = let Adder _ s = mapM toAdder xs in s  

main = print $ sum' [1..100]
--5050

Adder只是某种类型的包装器，它也保持“运行总和”。我们可以创建Adder一个 monad，它在这里做了一些工作：当操作>>=（又名“绑定”）执行时，它返回新结果和该结果的运行总和加上原始运行总和的值。该toAdder函数接受一个 Int 并创建一个Adder将该参数作为包装值和运行总和（实际上我们对值不感兴趣，而只对总和部分感兴趣）。然后 insum' mapM可以发挥它的魔力：虽然它的工作方式类似于map嵌入在 monad 中的值，但它执行“monadic”函数，例如toAdder，并将这些调用链接起来（它使用sequence去做这个）。在这一点上，我们通过 monad 的“后门”了解了标准map缺失的列表元素之间的交互。