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

Question

对于一个整数数组 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 编辑 ]

Answer 1

原帖由 drunkedcat 于 2009-3-29 21:37 发表
不是第一个零，是最后一个数，也就是全体元素的和，这个是不需要的。

需要多少就 take 多少不就得了。

Answer 2

大家的方法都很绚。
我来个笨的。
先写成scheme 一会再来翻译。。。。

2. (define (accumulated-sum lon)
3.   (cond
4.    [(empty? (cdr lon)) lon]
5.    [else (accumulated-add
6.           (car lon)
7.           (accumulated-sum (cdr lon)))]))
9. (define (accumulated-add n los)
10.   (cons (+ n (car los)) los))
12. (accumulated-sum '(4 3 2 1))
13. >(10 6 3 1)

复制代码

Answer 3

原帖由 drunkedcat 于 2009-3-29 20:47 发表

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

嫌那个 0？那用 scanl1 吧

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

复制代码

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

复制代码

Answer 7

原帖由 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]

Answer 8

c 中可以优化算法，进而提高程序运行效率
haskell 中需要考虑优化算法吗？
编译器会优化吧？

Answer 9

这个怎么样？

2. Prelude> let s=0:[x+y|x<-[1..7]|y<-s]
3. Prelude> s
4. [0,1,3,6,10,15,21,28]
5. Prelude>

复制代码

要带这个参数

-XParallelListComp