map-acc

こんな感じのsum-accを書きたかったんだけど，なかなか綺麗に書けない．

(sum-acc '(1 2 3 4)) ; => (1 3 6 10)

累積和のリストっていうのかな．

累積ってことでgauche.collectionのmap-accumを使ってみる．

(use gauche.collection)
(define (sum-acc lis)
  (values-ref (map-accum (lambda (i s)
                           (let1 n (+ i s)
                             (values n n)))
                         0
                         lis)
              0))

リストの要素にするのも累積するのも同じ値でいいのに，(values n n)とvalues-refが出てくるのが冗長に見えて仕方ない．

fold版．

(define (sum-acc lis)
  (cdr (reverse
        (fold (lambda (i r)
                (cons (+ i (car r)) r))
              '(0)
              lis))))

'(0)とcdr reverseが辻褄合わせにしか見えない．

unfold版．

(use srfi-1)
(define (sum-acc lis)
  (let1 f (lambda (x) (+ (car x) (cadr x)))
    (unfold (lambda (x) (null? (cdr x)))
            f
            (lambda (x) (cons (f x) (cddr x)))
            (cons 0 lis))))

unfoldはseedを一つしか持ち回れないので，ペアでゴリ押しすることになってしまう．そういえばgauche.collectionにはunfold系のメソッドがない気がする．
map-accumでは過剰でunfoldでは不足ということなのか？どうしてこうなった…

結局こうなった．

(define (map-acc f seed lis)
  (let loop ((seed seed) (lis lis))
    (if (null? lis)
        '()
        (let1 val (f (car lis) seed)
          (cons val (loop val (cdr lis)))))))

(define (sum-acc lis)
  (map-acc + 0 lis))

このmap-accは，map-accumのリストの要素と状態が同じ値になった版にも見えるし，foldのリストを作る版にも見えるし，unfoldが第一引数と第三引数の代わりにリストを受け取るような感じにも見える．
何故，foldとunfoldとmap-accumがあってこのmap-accに相当するものがないのか．

おまけのfold+副作用版

(define (sum-acc lis)
  (reverse!
   (rlet1 res '()
     (fold (lambda (i r)
             (rlet1 n (+ i r)
               (push! res n)))
           0
           lis))))

(追記 2011-02-02)
Haskellのscanlがこれだった．