[已解决] haskell 如何高效地计算部分和？

drunkedcat

对于一个整数数组 x，现在要计算它其中每个元素所在位置之前的各个元素的和，
例如，
x = [1,2,3,4,5,6,7]
要得到如下的结果
s = [0,1,3,6,10,15,21]

用 c 的方法，只要计算 6 次加法就可以得到以上结果。
用 haskell， 能这样高效地做吗？

我想到的很直接的做法是，

subsum x = map sum $ init $ inits x

但是觉得可能做会多余的计算。

不知道各位以为如何。谢谢了先。

[ 本帖最后由 drunkedcat 于 2009-3-29 20:52 编辑 ]

drunkedcat

原帖由 win_hate 于 2009-3-29 19:59 发表
这个怎么样？


Prelude> let s=0:[x+y|x


要带这个参数

-XParallelListComp

win_hate  兄说的正是，我也刚好想到这里了。

subsum xs = 0 : [x+y | (x,y) <- zip xs $ subsum xs]

drunkedcat

原帖由 MMMIX 于 2009-3-29 20:40 发表


Prelude> scanl (+) 0 [1..7]
[0,1,3,6,10,15,21,28]

MMMIX 一出手，更加简练，佩服，学习ing。只是要加上一个 init。

drunkedcat

不是第一个零，是最后一个数，也就是全体元素的和，这个是不需要的。