計算機プログラムの構造と解釈 第二版 P70 問題2.39

この問題は虫食い問題。

で、ポイントは、listはペア同士をくっつけたヤツなんだけど、
それがどういう風な構成になっていれば良いのかっていう事を
知っていれば出来ると思う。

consでいくか、appendをつかうか。みたいな。

あとはリストの左から評価されるか、右から評価されるかをふまえれば、
意外とカリッとできあがる。

実装

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(use ggc.debug.trace)
(use math.mt-random)

(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))

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

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

;; main
(define (main args)

  (display "(reverse-r '(1 2 3 4)): ")
  (display (reverse-r '(1 2 3 4)))
  (newline)

  (display "(reverse-l '(1 2 3 4)): ")
  (display (reverse-l '(1 2 3 4)))
  (newline)

  0)

実行

(reverse-r '(1 2 3 4)): (4 3 2 1)
(reverse-l '(1 2 3 4)): (4 3 2 1)

意外と簡単かも。