SICP

SICP を読んでみる #40 第二章 pp.55-58

MIT OCW のビデオは完全に先を行ってしまったっぽいので当分お休みして、追いつくまでは本文に集中します。

本文

2.2 階層データ構造と閉包性
ある集合の要素にある演算を作用させて得られた要素が、またその集合の要素だった場合に、要素の集合はその演算のもとで閉じているというのが本来の閉包の定義

対の car 部分に値、 cdr 部分に次の対へのポインタを格納することでリスト構造を表現する。
また、このための手続きとして list がある。

※Gauche の場合、nil は ()
註釈を見ると、nil の扱いはかなり議論の的になったようで、嗚呼、乙。。。という感じ。

リスト演算

問題解答

問 2.17

(define odds (list 1 3 5 7 9))

(define (last-pair items)
  (if (null? (cdr items))
      (car items)
      (last-pair (cdr items))))

(last-pair odds)

問2.18

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

  (reverse-iter (cdr items) (cons (car items) ())))

(define odds (list 1 3 5 7 9))

(reverse odds)

問2.19

(define (first-denomination coin-values)
  (car coin-values))

(define (except-first-denomination coin-values)
  (cdr coin-values))

(define (no-more? coin-values)
  (null? coin-values))

(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 us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(cc 100 us-coins)
(cc 100 uk-coins)

あまり深く考えずにペロッと書いたら正解っぽくなってしまってむしろキョドってしまった(汗

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です