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

この問題は、そもそも
map、append、lengthがどういう手続きか知らないと出来ない。
それは理解してると前提にする。

あとaccumulateの定義は説明のページに書いてあるので写す。

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

そんで後は、穴埋めするだけだ。
まず、mapに関して。

(define (map p sequence)
(accumulate (lambda (x y) < ? ? >)
nil
sequence))

ちょっと改行とか違うんだけども。
< ? ? >の所をどう埋めるか考える。

言えるのは、
・mapはリストを返すので、リストを作るようななんか。
・mapはリストの中身一個一個に、手続きを作用させるので、そんななんか。

リストの定義はこんな感じです。

(list 1 2 3 4)

は

(cons 1 
         (cons 2
                  (cons 3
                           (cons 4 nil))))

だので、後ろ側がリストだったらコリッとconsでくっつく！！

つぎappendなんだけど。

(define (append seq1 seq2)
(accumulate cons
< ? ? >
< ? ? >))

consは後ろ側にをガツっとlistをくっつける事が出来る。
accumulateの定義をよく見てみるとわかるけど、最後にseq2が初期値で呼び出されてくるので。
そこを意識してみるとうまく解けると思う。

つぎlength
これは考え方。
1をどんどん足していけば良いってのがみえればいい。
listの中に入っている値はほとんど無視しちゃう感じ。

実装

#!/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 (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) 
              nil 
              sequence))


(define (append seq1 seq2)
  (accumulate cons
              seq2
              seq1))


(define (length sequence)
  (accumulate (lambda (x y)
                (if (null? x)
                  y)  
                (+ y 1)) 
              0   
              sequence))

(define (square n)
  (* n n)) 


;; main
(define (main args)

  (display "(map square '(1 2 3 4 5)): ")
  (display (map square '(1 2 3 4 5)))
  (newline)

  (display "(append '(6 7 8 9) '(1 2 3 4 5)): ")
  (display (append '(6 7 8 9) '(1 2 3 4 5)))
  (newline)

  (display "(length '(1 2 3 4 5)): ")
  (display (length '(1 2 3 4 5 7)))
  (newline)

  0)

実行

(map square '(1 2 3 4 5)): (1 4 9 16 25)
(append '(6 7 8 9) '(1 2 3 4 5)): (6 7 8 9 1 2 3 4 5)
(length '(1 2 3 4 5)): 6

出来ている。