理系学生日記

おまえはいつまで学生気分なのか

問題2-39

fold-left、fold-rightを使ってreverseを作るよ。

(define (fold-right op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
	  (fold-right op initial (cdr sequence)))))

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
	result
	(iter (op result (car rest))
	      (cdr rest))))
  (iter initial sequence))

fold-leftの方はわりかし直感的で、こんな風なの書けばいいです。

(define (reverse sequence)
  (fold-left (lambda (x y) (cons y x)) () sequence))

でもでも、同じことをfold-rightでしようとするとはまる。

gosh> (define (reverse sequence)
	(fold-right (lambda (x y) (cons y x)) () sequence))
reverse
gosh> (reverse (list 1 4 9 16 25))
(((((() . 25) . 16) . 9) . 4) . 1)

こうかなー。もうちょっときれいな方法があるぽいけど。

(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) () sequence))