Schemeの課題 --- (3) 12-15

Copyright(C)1995,2006,2007,2013 by 桜川貴司
Copyright(C)1998-2005 by 日置尋久

ソーティング

データ列をその要素の大小順に従うように並び替える操作をソーティング (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]

  1. 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)
            ()
    

  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) で得られる.
  3. 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)のふるい」 のアルゴリズムを用いればよい.
    1. 2〜nまでの整数のリストを用意する.
    2. まずリストから2より大きい2の倍数を取り除く.
    3. 残っている要素のうち,2の次の要素をpとする.リストからpより大きいpの 倍数を取り除く. さらに残っている要素のうち,pの次の要素をあらためてpとして, 同様の操作を行う.
    4. このような操作を繰り返して,最後の要素までたどり着いたとき,残った 要素がn以下の素数となる.
    「エラトステネスのふるい」を1引数関数として定義した場合, それを用いるとprimesは,
            (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}について, 常にその上界と下界が存在するとき, 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端末の場合には,「端末」メニューの「文字コードの設定」で行える.

[kadai15opt][オプション問題]※必ずしも解かなくてよい
(メイルのサブジェクトは,kadai15optとすること)
指定した(議院|政党|選挙区)の国会議員データのリストを返す3引数関数
 (select  field-func  field-set  member-list)
を作成せよ.ここで,

なお,上記データファイル(parliament-utf8.scm)は,自分で作成するファイルから loadして使うこと. つまり,~/scheme/に保存して,
(load "parliament.scm")
とファイルに書いておけばよい.

<想定する使用例>
参議院議員のリスト
(select house '(sangiin) members-of-parliament)
自民党と民主党の議員のリスト
(select party '(jimin minshu) members-of-parliament)
京都,大阪,奈良から選出された議員のリスト
(select district '(kyoto osaka nara) members-of-parliament)
さらにこの関数selectと集合演算およびlistlen([kadai09])を用いて,以下を求めよ.
  1. 参議院の自民党と公明党と自由党の議員数の合計
  2. 衆議院の自民党,公明党,自由党以外の議員数の合計
  3. (選挙区が東京,大阪のいずれかであるかまたは自民党である)議員以外の議員の数
結果だけでなく,それを得るのに必要なschemeの式もあわせて提出すること.必要で あれば,適当な変数を定義して用いてもよい.

[参考]:関数を引数として扱う例

  ;; 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)


4回目(の説明)のまとめ

kadai08-kadai11のページへ