[已解决] 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 编辑 ]

win_hate

这个怎么样？

1. 
   
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

izhier

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

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]

MMMIX

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

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

复制代码

drunkedcat

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


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

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

MMMIX

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


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

嫌那个 0？那用 scanl1 吧

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

复制代码

drunkedcat

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

flw

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

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

DQP

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

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

复制代码