nilの代わりに'()を使用する。
2.17
(define (last-pair lis)
(if (null? (cdr lis))
lis
(last-pair (cdr lis))))
2.18
(define (reverse lis)
(define (reverse-iter lis reversed)
(if (null? lis)
reversed
(reverse-iter (cdr lis) (cons (car lis) reversed))))
(reverse-iter lis '()))
2.19 (引数にリストを取るcc)
(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))
(define first-denomination car)
(define except-first-denomination cdr)
(define no-more? null?)
2.20 (任意の数の引数を取る関数)
(define (same-parity fst . rest)
(define (same-parity-iter lis result)
(cond
((null? lis) (cons fst (reverse result)))
((eq? (even? fst) (even? (car lis))) (same-parity-iter (cdr lis) (cons (car lis) result)))
(else (same-parity-iter (cdr lis) result))))
(same-parity-iter rest '()))
2.21 (mapによる書き換え)
(define (square x)
(* x x))
(define (square-list items)
(if (null? items)
'()
(cons (square (car items)) (square-list (cdr items)))))
(define (square-list items)
(map square items))
2.22 (リストを反復的に処理する時のパターン)
省略。Gaucheのsrfiの実装なんかを見てると、処理を行なった要素をconsで(逆順に)蓄積していって、最後にreverse!して返す、ってパターンが多い。
2.23 (リストに対し順番に処理を行うfor-each)
(define (for-each proc lis)
(if (null? lis)
#t
(begin
(proc (car lis))
(for-each proc (cdr lis)))))
2.24 (リストによって作られる木構造)
省略。
2.25 (carとcdrでリストの要素にアクセス)
見やすいようにここだけquoteを使う。
(car (cdr (car (cdr (cdr '(1 3 (5 7) 9)))))) (car (car '((7)))) (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr '(1 (2 (3 (4 (5 (6 7))))))))))))))))))
2.26 (append,cons,list)
(define x (list 1 2 3)) (define y (list 4 5 6)) (append x y) ; => (1 2 3 4 5 6) (cons x y) ; => ((1 2 3) 4 5 6) (list x y) ; => ((1 2 3) (4 5 6))
2.27 (リスト中のリストも逆順にするdeep-reverse)
(define (deep-reverse lis)
(define (deep-reverse-iter lis reversed)
(if (null? lis)
reversed
(let ((first-item (car lis)))
(deep-reverse-iter (cdr lis)
(cons (if (pair? first-item) (deep-reverse first-item) first-item)
reversed)))))
(deep-reverse-iter lis '()))再帰は便利だ。
2.28 (tree中のleafを左から右に並べるfringe)
(define (fringe x)
(cond ((null? x) '())
((not (pair? x)) (list x))
(else (append (fringe (car x))
(fringe (cdr x))))))再帰は便利だ。
2.29 (モービル)
データ構造がしっかり頭に入ってないと混乱する。型づけができれば楽になりそうな。
(define (make-mobile left right)
(list left right))
(define (make-branch length structure)
(list length structure))
(define (left-branch mobile)
(list-ref mobile 0))
(define (right-branch mobile)
(list-ref mobile 1))
(define (branch-length branch)
(list-ref branch 0))
(define (branch-structure branch)
(list-ref branch 1))
(define mobile? pair?)
(define (total-weight mobile)
(define (total-weight-branch branch)
(let ((structure (branch-structure branch)))
(if (mobile? structure)
(total-weight structure)
structure)))
(+ (total-weight-branch (left-branch mobile))
(total-weight-branch (right-branch mobile))))
(total-weight
(make-mobile
(make-branch 1 10)
(make-branch 1
(make-mobile
(make-branch 1 5)
(make-branch 1 5)))))
(define (mobile-balanced? mobile)
(define (branch-torque branch)
(let ((structure (branch-structure branch)))
(if (mobile? structure)
(and (mobile-balanced? structure)
(* (branch-length branch) (total-weight structure)))
(* (branch-length branch) structure))))
(let ((torque-left (branch-torque (left-branch mobile)))
(torque-right (branch-torque (right-branch mobile))))
(and torque-left
torque-right
(= torque-left torque-right))))make-mobile, make-branchをリストでなくペアの構造にした時、変更しなければならないのはleft-branch, right-branch, branch-length, branch-structureだけ。Abstraction Barriarsってやつですな。
2.30 (木構造に対するマッピング)
(define (square-tree tree)
(cond ((null? tree) '())
((not (pair? tree)) (* tree tree))
(else (cons (square-tree (car tree))
(square-tree (cdr tree))))))
(define (square-tree tree)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(square-tree sub-tree)
(* sub-tree sub-tree)))
tree))例をコピペして書きかえただけ。
2.31 (木構造に対するマッピング; 抽象化)
(define (tree-map proc tree)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(tree-map proc sub-tree)
(proc sub-tree)))
tree))コピペできるってことは抽象化できるってこと。
2.32 (冪集合)
(define (subsets s)
(if (null? s)
(list '())
(let ((rest (subsets (cdr s))))
(append rest (map (lambda (r) (cons (car s) r)) rest)))))説明は省略。
