ソーティング
データ列をその要素の大小順に従うように並び替える操作をソーティング (sorting)と呼ぶ．たとえば，整数を要素とするリストをソートするとは，
(1 6 3 5 3) -> (1 3 3 5 6)
のようにリストの要素を並び替えることである．実数の大小比較には以下の関数を用いる．
<, <=, =, >, >=
ソーティングを行う一つの方法に以下のような挿入法がある． まず，次のような関数を考える．
この操作を挿入と呼ぶ．これは例えば，
(1 4 6 7 8)と5を引数にして，(1 4 5 6 7 8)を返すような関数である．
[kadai12]
(1) 「既に昇順にソートされている整数のリスト」に「整数」を挿入する
2引数関数insertを定義せよ．
;; 動作例
==> (insert 3 '(0 2 5 6 7))
(0 2 3 5 6 7)
;; 空リスト(0個の数値が並んだリスト)を与えた場合
==> (insert 2 '())
(2)
insertがあれば，次のようにしてソーティングを行うことができる． すなわち，まず空のリストを用意し，そこに引数のリストの要素を一つずつ挿入 する．すべてを挿入したら，その結果を返せばよい．
(2) 整数のリストをソートする1引数関数isortを，(1)のinsertを用いて定義せよ．
;; 動作例
==> (isort '(3 6 2 5 7 0))
(0 2 3 5 6 7)
・記号(symbol)のソーティング
文字列(string)の辞書式順序による大小比較には以下の関数を用いる
string<?, string<=?, string=?, string>?, string>=?
記号(symbol)の大小比較を直接行うことはできない．
その名前でなんらかの大小比較を行う場合は，文字列(string)に変換してから比較する．
例
==> (string<? (symbol->string 'aaa) (symbol->string 'abc))
#t
[kadai13]
記号のリストをソートする(記号の名前の辞書式順序で並べ
替える)1引数関数sisortを定義せよ．
※ もちろんinsertに相当する関数もあらためて作成することになる．
;; 動作例
==> (sisort '(c b a d ab))
(a ab b c d)
素数
素数とは，1と自分自身以外に約数をもたない1より大きい整数である． ここでは，素数のリストを生成する方法について，以下の手順で考える．
[kadai14]
- m以上n以下の整数のリスト
(m m+1 ... n)
を生成する2引数関数(generate-interval m n)を定義せよ． ただし，m > nの場合は，『( )』を返すものとする．;; 動作例 ==> (generate-interval 1 10) (1 2 3 4 5 6 7 8 9 10) ==> (generate-interval 10 10) (10) ==> (generate-interval 3 2) ()
- 整数のリストxからmの倍数を取り除く2引数関数(sieve-multiples m x)を定義せよ．
;; 動作例 ==> (sieve-multiples 2 '(2 3 4 5 6 7 8)) (3 5 7) ==> (sieve-multiples 3 '()) ()なお，xをyで割ったときの余りは， (modulo x y) で得られる．
- n以下の素数のリストを生成する1引数関数(primes n)を定義せよ．
;; 動作例 ==> (primes 10) (2 3 5 7) ==> (primes 100) (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
素数のリストを得るには，次の「エラトステネス(Eratosthenes)のふるい」 のアルゴリズムを用いればよい．- 2〜nまでの整数のリストを用意する．
- まずリストから2より大きい2の倍数を取り除く．
- 残っている要素のうち，2の次の要素をpとする．リストからpより大きいpの 倍数を取り除く． さらに残っている要素のうち，pの次の要素をあらためてpとして， 同様の操作を行う．
- このような操作を繰り返して，最後の要素までたどり着いたとき，残った 要素がn以下の素数となる．
(define (primes n) (eratosthenes (generate-interval 2 n)))とできる．また，「エラトステネスのふるい」を2引数関数として定義すること もできるだろう．
有限集合の演算
有限集合に関する演算を行う関数をSchemeで記述することを考える． 記号の有限集合は(同じ要素を2つ以上含まない)記号のリスト で表現することができる． また空集合は空リストで表すことができる．
'(a b c d) ;; a,b,c,dの四つの要素からなる集合 '( ) ;; 空集合
また，ある集合Sを一つ固定して，その部分集合全体の集合P Sを 考えると，P Sは部分集合の関係⊂によって半順序集合となる． さらに，P Sは，和集合と交集合の2つの演算∪，∩によって，完備ブール束となる．
半順序集合の定義集合Aに関係≦が定義され，x,y,z∈Aに対し，以下が成り立つとき， Aは関係≦により半順序集合となるという． このとき，≦をAの上の半順序関係という． また，半順序関係が定義されている集合を単に半順序集合という．
x≦x x≦y ∧ y≦x -> x=y x≦y ∧ y≦z -> x≦z上界と下界の定義
半順序集合Aの部分集合Bについて，
{x∈A|∀y∈B x≦y}
の元をBの下界(かかい)，
{x∈A|∀y∈B y≦x}
の元をBの上界(じょうかい)という． 上界や下界は存在しない場合がある．
上限と下限の定義半順序集合Aの部分集合Bについて， Bの上界のうち最小のものがあればそれを最小上界あるいは上限という． また，Bの下界のうち最大のものがあればそれを最大下界あるいは下限という． それぞれ ∨Bまたはlub(B)， ∧Bまたはglb(B)と書く． 上界や下界が存在しても，上限や下限が存在しない場合がある．
束の定義(1)半順序集合Aの任意の要素x,yについて， 常に{x,y}の上限と下限が存在するとき， Aを束(そく,lattice)という． この条件は，Aの空でない有限部分集合について常にその上限と下限が存在する ことと同値である(本によっては，空集合を含めた任意の有限部分集合について 上限と下限が存在することを束の定義にしている場合もある． この場合，束には最大元と最小元が存在することになる).
束には同値な別の定義がある．
束の定義(2)集合Aに2項演算∧と∨が定義され，以下の性質を満たす時，Aを束という．
x,y,z∈Aに対し，以下が成り立つ． x∧x=x x∧y=y∧x x∧(y∧z)=(x∧y)∧z x∨x=x x∨y=y∨x x∨(y∨z)=(x∨y)∨z (x∧y)∨x=x (x∨y)∧x=x分配束の定義
束Aについて以下が成り立つ時，Aを分配束という．
∀x,y,z∈A x∧(y∨z)=(x∧z)∨(y∧z)これは以下の条件と同値である．
∀x,y,z∈A x∨(y∧z)=(x∧z)∨(y∧z)最大元，最小元の定義
束Aに対し，その元xが以下を満たす時，xを最大元といい，1またはTと書く． 最大元が存在すれば，∧φ=1である．
∀y∈A y≦x
束Aに対し，その元xが以下を満たす時，xを最小元といい，0または⊥と書く． 最小元が存在すれば，∨φ=0である．
∀y∈A x≦y補元の定義
束Aには1と0が存在するとする． x∈Aについて以下を満たすy∈Aをxの補元という．
x∨y=1 x∧y=0
補元は存在するとは限らないし，存在したとしても複数存在する場合がある． しかし，分配束においては補元が存在すれば一意的である．
相補束の定義束Aに最大元と最小元があり， Aのすべての元について，その補元が一意的に存在する時，Aを相補束という． xの補元をここでは¬xと書くことにする．
ブール束の定義相補束かつ分配束であるような束Aをブール束という． ブール代数ともいう． 有限なブール束は，ある有限集合を束とみなしたものと同じ構造を持つ．
ブール代数Aの2つの二項演算∨と∧から，以下のように2つの演算+と*を定義すると， (A,+,*,0,1)は可換環となる．これをブール環という．
x+y = (x∧¬y)∨(¬x∧y) x*y = x∧y完備束の定義
束Aのすべての部分集合Bについて，Bの上限が存在する時，Aを完備束という． この条件は， 束Aのすべての部分集合Bについて，Bの下限が存在することと同値である． 有限な束は完備束である．
[kadai15]
記号の有限集合に関する以下の関数を作成せよ．
関数への引数が記号の有限集合を表す場合は，必ずそれら記号のリストで与えられ，そのリストには同じ要素が2つ以上含まれることはないと仮定する．
なお，二つの記号が等しいかどうかを判定するには，eq?を用いればよい．
==> (eq? 'x 'x) #t ==> (eq? 'x 'y) #f ==> (eq? 'x (car '(x y z))) #t
| element? |
xが集合Pの要素かどうかを判定する2引数関数 (xが集合Pの要素ならば#t，そうでなければ#fを返す) |
|---|---|
| subset? |
集合Pが集合Qの部分集合かどうかを判定する関数 (集合Pが集合Qの部分集合ならば#t，そうでなければ#fを返す) |
| intersection-set | 2つの集合P,Qの共通集合P∩Qを与える2引数関数 |
| union-set | 2つの集合P,Qの和集合P∪Qを与える2引数関数 |
| difference-set | 集合Pと集合Qの差集合P-Qを求める関数 (Pに属してQに属さない要素からなる集合) |
<動作例>
==> (element? 'd '(a b c d))
#t
==> (element? 'x '(a b c d))
#f
==> (element? 'x '())
#f
==> (subset? '() '())
#t
==> (subset? '() '(b c a d))
#t
==> (subset? '(a b) '(b c a d))
#t
==> (subset? '(a b d c) '(a b c d))
#t
==> (subset? '(a b c e) '(a b c d))
#f
==> (subset? '(a b c e) '())
#f
==> (intersection-set '(a b c d) '(c d e f))
(c d)
==> (intersection-set '(a b c d) '(e f))
()
==> (intersection-set '(a b c d) '())
()
==> (intersection-set '() '(e f))
()
==> (union-set '() '())
()
==> (union-set '(a b c d) '())
(a b c d)
==> (union-set '() '(c d e f))
(c d e f)
==> (union-set '(a b c d) '(c d e f))
(a b c d e f)
==> (union-set '(a b c d) '(e f))
(a b c d e f)
==> (difference-set '(a b c d e f) '())
(a b c d e f)
==> (difference-set '() '(a d f))
()
==> (difference-set '(a b c d e f) '(a d f))
(b c e)
==> (difference-set '(a b c d e f) '(b e c g a d f))
()
●応用問題[オプション]
※必ずしも解かなくてよいオプション課題．
2000年3月現在の国会議員(参院251名，衆院499名)のデータを
(名前 議院 政党 選挙区)
というリストのリストで表したものを
http://www.stdio.h.kyoto-u.ac.jp/~sakura/scheme/parliament-utf8.scm
に用意した(右クリック+名前をつけてリンク先を保存 などでファイルとして保存するか，コピー＆ペーストする．
コードがEUCのファイルもある:http://www.stdio.h.kyoto-u.ac.jp/~sakura/scheme/parliament-euc.scm)．ファイルには以下が定義されている．
| members-of-parliament | 上記の形式の国会議員データのリストのリスト |
|---|---|
| set-of-houses | 議院の集合 |
| set-of-parties | 政党の集合 |
| set-of-districts | 選挙区(都道府県，比例)の集合 |
| (house x) | 国会議員データxを引数として所属議院を返す関数(実体はcadr) |
| (party x) | 国会議員データxを引数として所属政党を返す関数(実体はcaddr) |
| (district x) | 国会議員データxを引数として所属選挙区を返す関数(実体はcadddr) |
なお，ファイルの日本語コードはEUCであるため，仮想端末等を利用している場 合には日本語文字コードをEUCに設定しないとうまく表示されない場合がある． 例えばGNOME端末の場合には，「端末」メニューの「文字コードの設定」で行える．
[kadai16opt][オプション問題]※必ずしも解かなくてよい
指定した(議院|政党|選挙区)の国会議員データのリストを返す3引数関数
(select field-func field-set member-list)
を作成せよ．ここで，
- 第1引数field-funcは上で定義した関数house,party,districtのいずれかである．
- 第2引数は，field-funcに対応した議院の集合，政党の集合，選挙区の集合のいずれかの部分集合である．
- 第3引数は，国会議員データのリストmembers-of-parliamentである．
(load "parliament.scm")とファイルに書いておけばよい．
<想定する使用例>
- 参議院議員のリスト
- (select house '(sangiin) members-of-parliament)
- 自民党と民主党の議員のリスト
- (select party '(jimin minshu) members-of-parliament)
- 京都，大阪，奈良から選出された議員のリスト
- (select district '(kyoto osaka nara) members-of-parliament)
- 自民党・公明党・自由党のどれかに属する参議院議員数
- 自民党・公明党・自由党のいずれにも属さない衆議院議員数
- (選挙区が東京，大阪のいずれかであるかまたは自民党に属しているような)議員以外の衆議院・参議院両方併せた議員数
[参考]:関数を引数として扱う例
;; 3引数関数(f op x y)
;; opが四則演算の演算子であれば，x,yをその演算子に適用した結果を返す．
;; そうでなければ，リスト(x y)を返す．
(define (f op x y)
;; listは引数をすべて並べたリストを返す．
(if (element? op (list + - * /))
(op x y)
(list x y)))
==> (f + 1 2)
3
==> (f * 3 4)
12
==> (f 1 2 3)
(2 3)
==> (f 'x 1 2)
(1 2)