SICP 2.2 Hierarchical Data and the Closure Property

漸く『データ構造』っぽい話。

ノート

階層データと閉包特性。
よくLISPの説明で見かけるcons cellの構造の図はbox-and-pointer notationと呼ぶらしい。
cell自体はポインタの組。ポインタの先は別のcons cellかbox。boxの中身は既出で言うと整数、小数、分数辺りか。いわゆる基本データ型のオブジェクト。

ここで出て来るclosureはいわゆるクロージャではなく再帰的なデータ構造を取れる『閉包特性』の事。

The ability to create pairs whose elements are pairs is the essence of list structure's importance as a representational tool. We refer to this ability as the closure property of cons.

ペアのポインタが（また自分自身と同じデータ構造である）ペアを指す事が出来る事（ability）を閉包特性と呼ぶらしい。データ構造がこの特性を持っている事でより複雑な階層データが構築出来る。

2.2.1 Representing Sequences

訳すとすれば『（データの）列の表現』。リストの事。
特に難しい事は何もない。

List operations

リストの操作。
例をDrRacket上で実際に動かしてみる。

> (define (list-ref items n)
    (if (= n 0)
        (car items)
        (list-ref (cdr items) (- n 1))))
define-values: cannot change constant variable: list-ref
> (list-ref (list 1 2 3) 2)
3
>

list-refはR5RSで定義されているので怒られる。仕様上予約語と言う訳ではないと思うが、標準で定義されている関数は再定義出来ない様にDrRacketは実装されている模様。
名前を変えて再チャレンジ。

> (define (my-list-ref items n)
    (if (= n 0)
        (car items)
        (my-list-ref (cdr items) (- n 1))))
> (define squares (list 1 4 9 16 25))
> (my-list-ref squares 3)
16
>

ちゃんと動く。lengthもR5RSで定義されているので名前を変える。

> (define (my-length items)
    (if (null? items)
        0
        (+ 1 (my-length (cdr items)))))
> (define odds (list 1 3 5 7))
> (my-length odds)
4
> (length odds)
4
>

iterativeパターンも動かしてみる。

> (define (my-length2 items)
    (define (length-iter a count)
      (if (null? a)
          count
          (length-iter (cdr a) (+ 1 count))))
    (length-iter items 0))
> (my-length2 odds)
4
>

appendも既に定義されているので。

> (define (append list1 list2)
    (if (null? list1)
        list2
        (cons (car list1) (append (cdr list1) list2))))
define-values: cannot change constant variable: append
> (define (my-append list1 list2)
    (if (null? list1)
        list2
        (cons (car list1) (my-append (cdr list1) list2))))
> (define squares (list 1 4 9 16 25))
> (define odds (list 1 3 5 7))
> (append squares odds)
(1 4 9 16 25 1 3 5 7)
> (append odds squares)
(1 3 5 7 1 4 9 16 25)
> (my-append squares odds)
(1 4 9 16 25 1 3 5 7)
> (my-append odds squares)
(1 3 5 7 1 4 9 16 25)
>

期待通り。

Exercise 2.17

リストの最後のペアとはcarに最後の要素、cdrにnullを持つペアの事。１要素のリストになる。

(define (last-pair lst)
  (if (null? (cdr lst))
      lst
      (last-pair (cdr lst))))

実行

> (last-pair (list 23 72 149 34))
(34)
>

Exercise 2.18

reverseもR5RSに定義されているので別名にする必要がある。
簡単に標準のappendを使うと：

(define (reverse1 lst)
  (if (null? (cdr lst))
      lst
      (append (reverse1 (cdr lst)) (list (car lst)))))

appendは毎回リストを全部走査してしまう筈なので何だか無駄が多い様に感じてしまう。consだけで組み立ててみる。
引数のリストと結果のリスト（初期値は空リスト）を用意して、再帰の度に引数リストの先頭を結果リストの先頭に移動させると、引数リストが空になった時に結果リストには逆向きのリストが出来てるかな。

(define (reverse2 lst)
  (define (last-in-first-out in out)
    (if (null? in)           
        out
        (last-in-first-out (cdr in) (cons (car in) out))))
  (last-in-first-out lst '()))

もう少し宣言的とういか気の利いた名前が付けられないものかとも思うが。
実行してみる。

> (reverse1 (list 1 4 9 16 25))
(25 16 9 4 1)
> (reverse2 (list 1 4 9 16 25))
(25 16 9 4 1)
> (reverse (list 1 4 9 16 25))
(25 16 9 4 1)
>

一応動いている。

Exercise 2.19

coin-valuesと言うリストに大きい順の貨幣の額が入っているとして。
元のfirst-denominationは引数に貨幣の種類の数を取って、その場合の最大の貨幣の額と言う定義だった。これを貨幣価値のリスト（coin-values）を取ってその最大値（大きい順に並んでいるのでその先頭要素）を返す関数に変更。

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

額の小さい方から対象とする貨幣の種類をひとつ減らすのに元々はkinds-of-coinsを１減らしていた部分に相当するexcept-first-denomination。貨幣価値リストの最大値以外のリストなので。

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

対象とする貨幣が無くなった事を元々はkinds-of-coinsが0になった事で判断していたが、今回は貨幣価値リストが空になった事で判断する。

(define (no-more? coin-values)
  (null? 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)
292
> (cc 100 uk-coins)
104561
>

uk-coinsの方は計算に少し時間が掛かる。

coin-valuesは1.2.2に倣って大きい順に計算する事を想定していたが、全ての組み合わせを網羅的に数え上げるだけなのでどのコインから数え始めても結果は変わらない。

> (define us-coins2 (list 1 5 10 25 50))
> (cc 100 us-coins2)
292
> (define us-coins3 (list 5 25 1 50 10))
> (cc 100 us-coins3)
292
>

Exercise 2.20

Schemeに於ける可変引数の書き方。
組み込みのeven?とodd?は使うとして、same-parityがやっている事は明らかにfilter。ただRacketのR5RSでfilterを使うには色々とややこしい状況がある模様。RacketあるいはR6RSでは特に問題はない。ここではR6RSで実装してみる。

#!r6rs
(import (rnrs lists (6))
        (rnrs base (6)))

(define (same-parity x . r)
  (filter (if (odd? x) odd? even?) (cons x r)))

実行してみる。

> (same-parity 1 2 3 4 5 6 7)
{1 3 5 7}
> (same-parity 2 3 4 5 6 7)
{2 4 6}
>

curly braceになるのがちょっと気になるが。結局の所、あまり標準に拘らず、また最新のRacketではなく昔のPLT Scheme互換（？）の#lang schemeで動かすのが本のサンプルとは一番違和感の無い結果を得られるのかも知れない。

Mapping over lists

mapの導入。
mapを使わないscale-listの定義は再帰を用いて要素ひとつひとつを順番に処理している様子が目立っている。一方mapを使う場合は全体を少し俯瞰して要素をひとつひとつ順番に処理する仕組みが隠されている。

Exercise 2.21

二つのsquare-listを実装。DrRacketではnilの代わりにnull。

(define (square-list1 items)
  (if (null? items)
      null
      (cons (* (car items) (car items)) (square-list1 (cdr items)))))
(define (square-list2 items)
  (map (lambda (x) (* x x)) items))

実行結果

> (square-list1 (list 2 3 4 5))
(4 9 16 25)
> (square-list2 (list 2 3 4 5))
(4 9 16 25)
>

Exercise 2.22

最初の定義。実際に動かしてみると

> (square-list (list 1 2 3 4))
(16 9 4 1)
>

答えが逆になってしまうのは、与えられたリストの先頭から計算しているくせに

(cons (square (car things))  answer)

と２乗した答えを、それまでの答えの前に追加してしまっている為。

かと言ってこのように逆にした所で

(cons answer (square (car things)))

動かしてみると

((((() . 1) . 4) . 9) . 16)

consの挙動は第１引数がリストの場合リストへのポインタと、値とのペアを作ってしまう。リストの要素は前にしか追加出来ないのでappendの様な関数が必要になる。

Exercise 2.23

引数のリストのcarに手続きを適用して（返って来る結果は無視して）cdrにfor-eachを再び適用する事になる。今まで出て来ていないと思うが、二つの関数を連続して呼び出す必要がある。ifは式しか取れないので複数の関数を連続して呼び出す事は出来ない。これまでに出て来ている文法だとcondやletを使う事になる。
condを使った回答

(define (for-each proc aList)
  (cond ((null? aList) (newline))
        (else (proc (car aList))
              (for-each proc (cdr aList)))))