計算機プログラムの構造と解釈 第二版 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
出来ている。