SICP 読み (19)

scheme SICP

2.2 節に突入。なかなかに進捗が微妙。

問題 2.17

解のみ。

(define (last-pair l)
 (let f ((l l))
   (if (null? (cdr l))
       l
       (f (cdr l)))))

問題 2.18

これも解のみ。

(define (reverse l)
 (let f ((l l) (result '()))
   (if (null? l)
       result
       (f (cdr l) (cons (car l) result)))))

問題 2.19

以下が解。

(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
	((or (< amount 0) (no-more? coin-values)) 0)
	(else
	 (+ (cc amount
		(except-first-denomination coin-values))
	    (cc (- amount
		   (first-denomination coin-values))
		coin-values)))))

(define (no-more? l) (null? l))

(define (except-first-denomination l) (cdr l))

(define (first-denomination l) (car l))

勘違いしていて、no-more? を以下のように定義していた。

(define (no-more? l)
  (null? (cdr l)))

いかんいかん。

gosh> (cdr (cdr (cdr (cdr us-coins))))
(1)
gosh> (no-more? (cdr (cdr (cdr (cdr us-coins)))))
#t
gosh>

問題 2.20

これも以下に解を。そろそろ試験ドリブンなソレにした方が良いかも。

(define (same-parity x . y)
  (define (f proc l result)
    (if (null? l) 
	result
	(f proc (cdr l) (if (proc (car l))
			    (append result (list (car l)))
			    result))))
  (if (odd? x)
      (f odd? y (list x))
      (f even? y (list x))))

なんか微妙。
しかも最初は以下な形になってて動かず。

(define (same-parity x . y)
  (define (f proc l result)
    (if (null? l) result)
    (f proc (cdr l) (if (proc (car l))
			(append result (list (car l)))
			result)))
  (if (odd? x)
      (f odd? y (list x))
      (f even? y (list x))))

よく考えたら l が null でも result 返却で処理が終わらんのよね。駄目だ。
てーか、上記の解はもう少しええ感じにならんかのぅ。

問題 2.21

これも解のみを。

(define (square-list items)
  (if (null? items)
      '()
      (cons (* (car items) (car items)) (square-list (cdr items)))))

(define (square-list items)
  (map (lambda (x) (* x x)) items))

なんか微妙。どんどん次行こう。

問題 2.22

あえて動作確認せず、検討してみる。
まず最初のは反復な iter に渡す cons があれでは逆になるだろ。ただし次のソレにある通り、引数を逆にすればなんとかなる、とゆー話ではない。
こんなリストができるに違いない。

((() . 1) . 4)

これ式のナニを何度か作りましたが、cons は微妙。

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
	answer
	(iter (cdr things)
	      (append answer (list (square (car things)))))))
  (iter items '()))

面倒臭いので cons 使って作ってから reverse ってワザをよく使ってた記憶あり。

問題 2.23

適当にヤッツケちゃってる感満載ですな。

(define (for-each proc list)
  (let f ((l list))
    (cond ((null? l) #t)
	  (else
	   (proc (car l))
	   (f (cdr l))))))

2.2.2 以降、どんどんハードルが高くなってきそう。今までの答え合わせもしたいんですが。