SICP q2.39

gistfile1.scm

(define nil '())

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

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

;----------------------------------------------------------------------------
; (list 1 2 3 4)
; のとき
; (list 4 3 2 1)
; (cons 4 (cons 3 (cons 2 (cons 1 nil))))
;
; fold-rightの場合、
; 始めのx,yに4とnilが入り、
; 次のx,yに3と「4とnilの結果」が入り…
; と進むのでconsで繋げるのは面倒そう
; （毎回「nilを差している値」を見つけ、それがxを指すようにしないといけないため）
; ということでq2.33のappendを使ってlistを繋げて行く
;
; yには今までの結果のlistが入っていて、その後ろに値xをlistにしてappendすればいい
(define (append seq1 seq2)
  (accumulate cons seq2 seq1))
(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) nil sequence))

(print (reverse (list 1 2 3 4)))

;----------------------------------------------------------------------------
; (list 1 2 3 4)
; のとき
; (list 4 3 2 1)
; (cons 4 (cons 3 (cons 2 (cons 1 nil))))
;
; fold-leftの場合、
; 始めのx,yにnilと1が入り、
; 次のx,yに「nillと1の結果」と2が入り…
; と続くため、それをそのままconsに与えればよい
(define (reverse sequence)
  (fold-left (lambda (x y) (cons y x)) nil sequence))

(print (reverse (list 1 2 3 4)))