問題 2.18

(define squares (list 1 4 9 16 25))
(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

;初めに以下を考えた。
(define (reverse items)
  (if (null? (cdr items))
      items
      (cons (reverse (cdr items)) (car items))))

;しかし、これでは
;(reverse squares)
;-> (((((25) . 16) . 9) . 4) . 1)
;となってしまう。
;そのまま鏡のように逆にするのではなく、
;(25 . (16 . (9 . (4 . (1)))))
;になるようにしないといけない。

(define (reverse items)
  (define (reverse-iter i p)
    (if (null? (cdr i))
        (cons (car i) p)
        (reverse-iter (cdr i) (cons (car i) p))))
  (reverse-iter items null))

;こうすると、
;(reverse squares)
;-> (25 16 9 4 1)
;できた。

;ちなみに、初めに考えた形でも、
;もし、木構造再帰的なcons連結をすべて、左から右の形にならべかえる
;関数(flattern list)があれば、形をほとんど変えずに定義できる。

(define (reverse items)
  (if (null? (cdr items))
      items
      (flattern (cons (reverse (cdr items)) (car items)))))

;では(flattern list)は定義できないか？

(define (flattern items)
  (append (if (pair? (car items))
              (flattern (car items))
              (cons (car items) null))
          (if (null? (cdr items))
              null
              (if (pair? (cdr items))
                  (flattern (cdr items))
                  (cons (cdr items) null)))))

;(flattern (cons (cons (cons 1 (cons 2 3)) 4) (cons 5 6)))
;-> (1 2 3 4 5 6)
;多少骨がおれたが、ちゃんと動いている。

;ここで、
;(reverse squares)
;-> (25 16 9 4 1)
;ok

;だが、このflatternはappend中でも再帰するため、
;ものすごく非効率な関数である。
;もうすこし効率的に、また、反復的に書けないだろうか…。