累積関数

変数 x = xk の値とそこでの関数の値 f(xk) = vk の組のリスト '( (x1 v1) (x2 v2) (x3 v3) ...) から累積関数の値のリスト '( (x1 v1) (x2 (+ v1 v2)) (x3 (+ v1 v2 v3)) ...) への変換はfold (foldl) を使うとどう書けるか．いや，先週，磁場の計算をやってて実際に必要になったのですよ...

nodakai@co:~$ ledit gosh -i
gosh> (use srfi-1)
(#<module srfi-1> #<module gauche.interactive>)
gosh> fold        
#<closure 0x8155960(kons knil lis1 lists)>
gosh> (define xy '((1 1) (2 4) (3 9) (4 16)))
xy
gosh> (reverse (cdr (fold (lambda (e acc) (let ((s (car acc)) (l (cadr acc)) (x (car e)) (v (cadr e)))
                                            (list (+ s v) (cons (list x (+ s v)) l))))
                          (list 0 '()) xy)))
((1 1) (2 5) (3 14) (4 30))

（追記： () にquoteを付け忘れていた，と言うかあえてquoteを外した書き方をしたら外し過ぎていたのを直した）
Mathematicaだとリストの末尾にも要素を付け加えられるから最後に逆順にしなくてもよい．Ocamlなら

nodakai@co:~$ ledit ocaml
        Objective Caml version 3.08.3

# open List;;
# fold_left;;
- : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
# let xy = [(1,1);(2,4);(3,9);(4,16)];;
val xy : (int * int) list = [(1, 1); (2, 4); (3, 9); (4, 16)]
# rev (snd (fold_left (fun (s,l) (x,v) -> (s+v,(x,s+v)::l)) (0,[]) xy));; 
- : (int * int) list = [(1, 1); (2, 5); (3, 14); (4, 30)]

うむ，やはりこの程度だと演算子とパタンマッチのあるOcamlの方が見やすいっすね... でもパタンマッチなら（ライブラリとして）Gaucheでも使える．ついでにquasiquoteで微妙に文字数を短くして...

gosh> (use util.match)                                                      
(#<module util.match> #<module srfi-1> #<module gauche.interactive>)
gosh> (reverse (cadr (fold (match-lambda* (((x v) (s l)) `(,(+ s v) ,(cons `(,x ,(+ s v)) l)))) '(0 ()) xy)))
((1 1) (2 5) (3 14) (4 30))