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

この問題もずるっこい感じで初めは考えた。


この前の問題で、appendっていうlistとlistをくっつけちゃってくれる
手続きをつくったのでそれを利用する方法。
reverseを再帰しつつつくれそうだ。


そんなずるっこい方法でやってたら、
勉強会の時に、appendなしでやってみようコーナーがはじまったので、
そもそもリストは対のあつまりだから、、、
みたいなかんじで考えていたら、意外と解けた。
テイルリカージョンになってるし、多分この方法の方が良い感じで早い。


実装

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

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

(define one-through-four (list 1 2 3 4)) 

(define squares (list 1 4 9 16 25))

(define odds (list 1 3 5 7)) 


(define (list-ref items n)
  (if (= n 0)
    (car items)
    (list-ref (cdr items) (- n 1))))


(define (length items)
  (if (null? items)
    0   
    (+ 1 (length (cdr items)))))


(define (length items)
  (define (length-iter a count)
    (if (null? a)
      count
      (length-iter (cdr a) (+ 1 count))))
  (length-iter items 0)) 


(define (append list1 list2)
  (if (null? list1)
    list2
    (cons (car list1) (append (cdr list1) list2))))

;;2.17
(define (last-pair items)
  (list-ref items (- (length items) 1)))

;;2.18
(define (reverse items)
  (if (null? items)
    items
    (append (reverse (cdr items)) (list (car items)))))


(define nil '())

(define (reverse items)
  (define (reverse-in vs result)
    (if (null? vs)
      result
      (reverse-in (cdr vs) (cons (car vs) result))))
  (reverse-in items nil))


;; main
(define (main args)

  (display "one-through-four: ")
  (display one-through-four)
  (newline)

  (display "squares: ")
  (display squares)
  (newline)

  (display "odds: ")
  (display odds)
  (newline)

  (display "(reverse one-through-four): ")
  (display (reverse one-through-four))
  (newline)

  (display "(reverse squares): ")
  (display (reverse squares))
  (newline)

  (display "(reverse odds): ")
  (display (reverse odds))
  (newline)
  0)


実行

one-through-four: (1 2 3 4)
squares: (1 4 9 16 25)
odds: (1 3 5 7)
(reverse one-through-four): (4 3 2 1)
(reverse squares): (25 16 9 4 1)
(reverse odds): (7 5 3 1)


OK