- 例：有理数の算術演算
- 抽象の壁
- データとは何か
- 拡張問題：区間算術演算
2.1 はざっくり言うとlistの使い方だ。 そういう概念がないものとして、そこにデータをまとめるという概念を伝えようとしている。 がっつりプログラミングをしているぼくらにはあまり必要のない情報だ。
今のリッチな言語は配列でメモリを意識することは少ないと思うけど、C などは配列の参照はまんまメモリの参照だ。 ポインタも配列も大した違いはない。 値１つ辺りのサイズをそれを領域とって並べているだけ。
a[0] : (*p + 0)
a[1] : (*p + 1)
a[2] : (*p + 2)
a[3] : (*p + 3)
だから型が違うとサイズも変わるため異なる型の値を格納することができない。 汎用性は低いが速い。
cons: CONStruct ペアを作る
(define pair (cons 1 2))
car: Contents of Address part of Register ペアの前
(car pair) => 1
cdr: Contetns of Decrement part of Register ペアの後
(cdr pair) => 2
- 並びの表現
- 階層構造
- 公認インターフェースとしての並び
- 例：図形言語
閉包性とは図2.4 の話
(define (last-pair a)
(if (null? (cdr a))
(car a)
(last-pair (cdr a))))
任意引数
(define (f x y . z) _body_)
x: 値１
y: 値２
z: リスト
pair?
(pair? ()) => #t
(pair? 1) => #f
null?
(null? ()) => #t
(null? (list 1)) => #f
(null? 1) => #f
map
(map (lambda (x) (+ x 1)) (list 1 2 3))
for-each
(for-each (lambda (x) (print x)) (list 1 2 3))
問題2.25 は簡単だからみんなでやってみよう
scale-tree をかいてみよう
(define (scale-tree-map tree factor)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(scale-tree-map sub-tree factor)
(* sub-tree factor)))
tree)) def scale_tree_map tree, fact
tree.map do |t|
if t.class == Array
scale_tree_map t,fact
else
t*fact
end
end
end- enumrate (iota)
- filter
- map
- accumulate (fold-right)
even-fibs を書いてみる
(define (ef n)
(define (next k)
(if (> k n)
()
(let ((f (fib k)))
(if (even? f)
(cons f (next (+ k 1)))
(next (+ k 1))))))
(next 0)) (define (even-fibs n)
(fold-right cons
()
(filter even?
(map fib
(iota n 1))))) (define (list-fib-squares n)
(fold-right cons
()
(map square
(map fib
(iota n)))))(define (flatmap proc seq)
(fold-right append () (map proc seq)))
(define (permutations s)
(if (null? s)
(list ())
(flatmap (lambda (x)
(map (lambda (p) (cons x p))
(permutations (delete x s))))
s)))def permutations (list)
if list.empty?
[[]]
else
list.map { |x|
permutations(list - [x]).map do |a|
[x] + a
end
}.reduce(:+)
end
end成層設計(stratified design)が大事
- クォート
- 例：記号微分
- 例：集合の表現
- 例：Huffman符号化木
'() を使うと中の記号を文字として認識して処理します。 リストを簡単に記述するのにも有用。
> (list a b c) ;=> ERROR
> '(a b c) ;=> (a b c)
> '(1 (2 3 4) 5) ;=> (1 (2 3 4))
> (cdr '(1 (2 3 4) 5)) ;=> ((2 3 4) 5)
> (+ 1 (car '(1 a))) ;=> 2memq は [R5RS] に含まれています。
> (memq 'a '(a b c)) ;=> (a b c)
> (memq '(a) '(a b c)) ;=> #f木の構築や探索に関する内容。 面白いし有益だとは思うのだけどちょっと興味薄いので飛ばします。
BTree の分かりやすいページを発見しました http://blog.h13i32maru.jp/blog/2012/07/01/btree/
線形探索を行うよりも索引を作ったほうが高速に探索でき、その索引の実装としては二分探索木やBTreeがあります。ハードディスクとの相性を考えるとBTreeのほうが優位なため、Indexの実現にBTreeが使われています。
Huffman符号化と言えば Deflate で使われているので有名ですね。zlib や gzip で使われているあれです。
長いテキストがあったとして、文字の出てくる頻度を文字ごとにカウントして、頻度の多い文字ほど少ないビット数で表すことによって文章を圧縮できたりします。