reducel/reducer Scheme編

Scheme 
(define (reducer kons ls)
  (if (< (length ls) 2)
      (car ls)
      (kons (car ls) (reducer kons (cdr ls)))))

(define (reducel kons ls)
  (let ((ls (reverse ls)))
    (letrec ((iter
	      (lambda (kons ls)
		(if (< (length ls) 2)
		    (car ls)
		    (kons (iter kons (cdr ls)) (car ls))))))
      (iter kons ls))))

Scheme はよく知らないけど、length は eager リストの長さに比例したコストがかかるのではないのかな。もしそうなら

(< (length ls) 2)

は

(null? (cdr ls))

か、もうすこしまじめには

(or (not (pair? ls)) (null? (cdr ls)))

のほうがいいんではなかろうか。
てか、reducel のほうは簡単に末尾再帰で定義できるよね。

(define (reducel-0 f ls)
  (if (null? (cdr ls))
      (car ls)
      (reducel-0 f (cons (f (car ls) (cadr ls)) (cddr ls)))))

(define (reducer f ls)
  (reducel-1 (lambda (x y) (f y x)) (reverse ls)))

て、書いていて気づいたけど、これ foldl を定義してそれを使って定義したほうがいいんじゃないだろうか。

(define (foldl f init ls)
  (if (null? ls) 
      init
      (foldl f (f init (car ls)) (cdr ls))))

(define (reducel-1 f ls)
  (foldl f (car ls) (cdr ls)))

で、どうせなので適当に length を使ったものと速度比較。

(define (reducel-0 f ls)
  (if (null? (cdr ls))
      (car ls)
      (reducel-0 f (cons (f (car ls) (cadr ls)) (cddr ls)))))

(define (foldl f init ls)
  (if (null? ls) 
      init
      (foldl f (f init (car ls)) (cdr ls))))

(define (reducel-1 f ls)
  (foldl f (car ls) (cdr ls)))

(define (reducel-2 f ls)
  (if (< (length ls) 2)
      (car ls)
      (reducel-2 f (cons (f (car ls) (cadr ls)) (cddr ls)))))

(use srfi-1)
(define (main args)
  (let ((ls (iota 20000 1)))
    (time (reducel-0 + ls))
    (time (reducel-1 + ls))
    (time (reducel-2 + ls))))

結果

;(time (reducel-0 + ls))
; real   0.014
; user   0.010
; sys    0.000
;(time (reducel-1 + ls))
; real   0.005
; user   0.010
; sys    0.000
;(time (reducel-2 + ls))
; real   0.856
; user   0.810
; sys    0.000

ふむ。やっぱり length の使用は控えるべきな気がする。