これまで，構造のあるデータを表現するための手段としては組
を用いてきた．ここではリスト(lists)という，
「データの(有限)列」を表現するデータ構造をみていく．
リストは構造自体が再帰的である．また，格納するデータの種類
が変わりうるという意味で多相的であるという特徴をもっている．
まずは簡単なリストの例を見てみよう．リストはデータ列を構成する
要素を ; で区切り，[]で囲むことで構成される．
# [3; 9; 0; -10];;
- : int list = [3; 9; 0; -10]
# let week = ["Sun"; "Mon"; "Tue"; "Wed"; "Thu"; "Fri"; "Sat"];;
val week : string list = ["Sun"; "Mon"; "Tue"; "Wed"; "Thu"; "Fri"; "Sat"]
リストの式には ``⟨ 要素の型 ⟩ list'' という
型が与えられる．これが意味するのは「(Objective Caml では)一つの
リストに並ぶ要素の型は同じ」でなければならない，という
ことである．また別の見方をすると，リスト式はその列の長さに関わらず，要
素の型が同じであれば，同じリスト型に属するということである．
# [1; 'a'];;
[1; 'a'];;
^^^
This expression has type char but is here used with type int
# (* compare with the type of [3; 9; 0; -10] *)
# [-3];;
- : int list = [-3]
このことは組とリストの決定的な違いであるので注意すること．
組の型は各要素の型を並べることで記述されるため，各要素の型は
異ってもよいが，大きさの違う組は同じ型に属し得ない(すなわち，
組の大きさの情報が型に現れている)．
リストの構造は，組のように「要素を並べたもの」と思う代りに，
以下のように再帰的に定義されている構造とも考えられる．つまり
-
[] は，空リスト(empty list, null list)と呼ばれ，
リストである．
- リスト l の先頭に(lの要素と同じ類いの)要素
e を追加したもの (e :: l と書く)
もリストである．
と定義することもできる．この定義は二番目の節が再帰的になっている．
:: のことをcons オペレータ(または単に cons)と呼ぶこともある．
このようにリストを構築する例を見てみよう．
# let oddnums = [3; 9; 253];;
val oddnums : int list = [3; 9; 253]
# let more_oddnums = 99 :: oddnums;;
val more_oddnums : int list = [99; 3; 9; 253]
# (* :: is right associative, that is, e1 :: e2 :: l = e1 :: (e2 :: l) *)
# let evennums = 4 :: 10 :: [256; 12];;
val evennums : int list = [4; 10; 256; 12]
# [];;
- : 'a list = []
要素を列記する方法と :: を用いる方法を混ぜることもできる．
evennums の例に見るように，:: は右結合する(e1 :: e2 :: l は
e1 :: (e2 :: l) と読む)． 空リスト [] は要素がなく，どのような要素
のリストとも見なせること ができるため，'a list という多相型が与えら
れている．もちろん，空リストには様々な型の要素を追加することができる．
# let boollist = true :: false :: [];;
val boollist : bool list = [true; false]
# let campuslist = "Yoshida" :: "Uji" :: "Katsura" :: [];;
val campuslist : string list = ["Yoshida"; "Uji"; "Katsura"]
ちなみに Objective Caml では「要素を並べる」定義は，(内部的には)再帰的な定義の
略記法である．つまり，
[e1; e2; ⋯ ; en] = e1 :: e2 :: ⋯ :: en :: []
である．
cons オペレータ :: は，あくまで「一要素の(先頭への)追加」
を行うもので，リストにリストを追加(連結)するという操作や，リストの最後
尾へ要素を追加するといった操作は :: で行えない．
# [1; 2] :: [3; 4];;
[1; 2] :: [3; 4];;
^
This expression has type int but is here used with type int list
# [1; 2; 3] :: 4;;
[1; 2; 3] :: 4;;
^
This expression has type int but is here used with type int list list
:: は文法キーワードなので，:: の型を見ることはできないが，
敢えて型を考えるなら 'a -> 'a list -> 'a list と思うのがよいだろう．
リストはどんな値でも要素にでき，関数のリスト，リストのリスト等を考える
ことも可能である．
# [(fun x -> x + 1); (fun x -> x * 2)];;
- : (int -> int) list = [<fun>; <fun>]
# [1; 2; 3] :: [[4; 5]; []; [6; 7; 8]];;
- : int list list = [[1; 2; 3]; [4; 5]; []; [6; 7; 8]]
2番目の例は，整数リストのリストに整数リストを :: で追加している．
| 5.2 |
リストの要素へのアクセス: match式とリストパターン |
|
さて，リストの要素にアクセスするときには組と同様にパターンを用いる．
リストパターンは
[⟨ パターン1 ⟩; ⟨ パターン2 ⟩; ...; ⟨ パターンn ⟩]
で n 要素のリスト(n が 0 なら空リスト)にマッチさせることができ
る．また，:: を使ってパターンを記述することもできる．
⟨ パターン1 ⟩ :: ⟨ パターン2 ⟩
と書いて，先頭の要素を ⟨ パターン1 ⟩ に，残りのリストを
⟨ パターン2 ⟩にマッチさせることができる．次の関数は，
三要素の整数リストの要素の和を計算する関数である．
# (* equivalent to
# let sum_list3 (x :: y :: z :: []) = x + y + z *)
# let sum_list3 ([x; y; z]) = x + y + z;;
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
let sum_list3 ([x; y; z]) = x + y + z;;
^^^^^^^^^^^^^^^^^^^^^^^
val sum_list3 : int list -> int = <fun>
リスト式の場合と同様，[x; y; z] というパターンは :: と [] を
使ったパターンで表すことができる．ここで，重要なことはこの関数を
コンパイルをするとコンパイラから警告が発せられていることである．
この ``nonexhaustive pattern'' と呼ばれる警告は，「パターンの表す型に
属する値でありながら，パターンにマッチしない値が存在する」という
意味であり，コンパイラはマッチしない値の例を示してくれる．
たしかにこの例では引数の型は int list であるにも関わらず
三要素のリストにしかマッチしない．実際，マッチしない値に関数を適用すると
マッチングに失敗したという例外が発生する．
# sum_list3 [4; 5; 6];;
- : int = 15
# sum_list3 [2; 4];;
Exception: Match_failure ("", 27, 14).
では，任意の長さの整数リストの要素の和を取る関数を書くにはどうすれば
よいのだろうか? 例え，二要素のリストの和を取る関数，四要素リストの和を
取る関数などなどを定義し，それを何らかの手段で組み合わせることができた
としても，それでは不十分である．関数定義の大きさが無限に長くなってしま
う!
ここで，リストが再帰的な定義をされた構造であることが非常に重要な意味を持っ
てくる．つまり，リストの再帰的な定義から，要素の和を取る定義を導くこと
ができるのである．それが以下の定義である．
-
空リストの全要素の和は 0 である．
- 先頭要素が n で，残りのリスト l に対する全要素の和を
s とすると，n :: l の全要素の和は
n + s である．
ポイントは，長いリストの全要素の和はより短いリストの全要素の和
から計算できることである．(fact などの定義と比べてみよ．)
これを Objective Caml の定義とするためには，与えられたリストが空かそうでない
かを判断する手段が必要であるが，ひとまず例を見て，その判断をどのように行うか
見てみよう．
# let rec sum_list l =
# match l with
# [] -> 0
# | n :: rest -> n + (sum_list rest);;
val sum_list : int list -> int = <fun>
まず，sum_list は再帰関数になっている． match 以下が l
が空リストかそうでないかを判断し，分岐処理を行っている部分で
match式と呼ばれる．match式の一般的な文法は，
match ⟨ 式0 ⟩ with ⟨ パターン1 ⟩ -> ⟨ 式1 ⟩ | ... | ⟨ パターンn ⟩ -> ⟨ 式n ⟩
という形で与えられ，⟨ 式0 ⟩を評価した結果を，⟨ パターン1 ⟩
から順番にマッチさせていき，⟨ パターンi ⟩でマッチが成
功したら，⟨ 式i ⟩を評価する．全体の値は⟨ 式i ⟩の値である．
各パターンで導入された変数 (上の例では n, rest) は対応する式の中だけで有効で
ある．上の Objective Caml による定義が，自然言語による定義に対応していることを
確かめよ．多くのリストを操作する関数は sum_list のように，
空リストの場合の処理と，cons の場合の処理を match で組み合わせて
書かれる．
match式についての注意
match 式がマッチングを順番に行う，というのは非常に重要な
点である．もしも，同じ値が複数のパターンにマッチする場合は先に
書いてあるパターンにマッチしてしまう．このような例は特に定数パ
ターンを使用すると発生しやすい．定数パターンは整数，文字列定数を
パターンとして用いるもので，その定数にのみマッチする．また，
前に書いてあるパターンのせいで，パターンにマッチする値がない場合，
コンパイラは ``this match case is unused.'' と警告を発する．
# let f x =
# match x with (1, _) -> 2 | (_, 1) -> 3 | (1, 1) -> 0 | _ -> 1;;
Warning: this match case is unused.
match x with (1, _) -> 2 | (_, 1) -> 3 | (1, 1) -> 0 | _ -> 1;;
^^^^^^
val f : int * int -> int = <fun>
# f (1, 1);;
- : int = 2
(1, 1) は最初のパターンにマッチする．また，3番目のパターンは
決して使われないので警告が出ている．
さて，一般的なリスト操作関数の例を見ていく前に，もうひとつ例をみていこ
う．(空でない)整数リストのなかから最大値を返す関数 max_list は
# let rec max_list l =
# match l with
# [x] -> x
# | n1 :: n2 :: rest ->
# if n1 > n2 then max_list (n1 :: rest) else max_list (n2 :: rest);;
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
..match l with
[x] -> x
| n1 :: n2 :: rest ->
if n1 > n2 then max_list (n1 :: rest) else max_list (n2 :: rest)..
val max_list : 'a list -> 'a = <fun>
のように定義される．
さて，リストに対する基本的な操作(構成と要素アクセス)をみたところで，
様々なリスト操作を行う関数を見ていこう．多くの関数がリストの構造に関し
て再帰的に定義される．また，ほとんどすべての関数が要素型によらない定義
をしているため，多相型が与えられることに注意しよう．
hd, tl, null
リストの先頭要素，リストの先頭を除いた残りを返す関数 hd (head の略), tl
(tail の略) は以下のように定義され，
# let hd (x::rest) = x
# let tl (x::rest) = rest;;
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
Characters 29-45:
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
let hd (x::rest) = x
^^^^^^^^^^^^^
let tl (x::rest) = rest;;
^^^^^^^^^^^^^^^^
val hd : 'a list -> 'a = <fun>
val tl : 'a list -> 'a list = <fun>
空リストに対しては働けない nonexhaustive な関数である．null は
与えられたリストが空かどうかを判定する関数である．
# let null = function [] -> true | _ -> false;;
val null : 'a list -> bool = <fun>
function キーワードは fun と match を組み合わせて匿名関数を定
義するもので，
function ⟨ パターン1 ⟩ -> ⟨ 式1 ⟩ | ... | ⟨ パターンn ⟩ -> ⟨ 式n ⟩
で
fun x -> match x with ⟨ パターン1 ⟩ -> ⟨ 式1 ⟩ | ... | ⟨ パターンn ⟩ -> ⟨ 式n ⟩
を示す．最後に受け取った引数に関して即座にパターンマッチを行うような
関数定義の際に便利である．
nth, take, drop
次は，n番目の要素を取り出す nth, n番目までの要素の
部分リストを取り出す take，n番目までの要素を抜かした
部分リストを取り出す drop である．リストの要素は先頭を一番目とする．
# let rec nth n l =
# if n = 1 then hd l else nth (n - 1) (tl l)
# let rec take n l =
# if n = 0 then [] else (hd l) :: (take (n - 1) (tl l))
# let rec drop n l =
# if n = 0 then l else drop (n - 1) (tl l);;
val nth : int -> 'a list -> 'a = <fun>
val take : int -> 'a list -> 'a list = <fun>
val drop : int -> 'a list -> 'a list = <fun>
これらの関数はリストの構造でなく，nに関しての再帰関数に
なっている．
# let ten_to_one = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1; 0];;
val ten_to_one : int list = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1; 0]
# nth 4 ten_to_one;;
- : int = 7
# take 8 ten_to_one;;
- : int list = [10; 9; 8; 7; 6; 5; 4; 3]
# drop 7 ten_to_one;;
- : int list = [3; 2; 1; 0]
# take 19 ten_to_one;;
Exception: Match_failure ("", 48, 7).
length
次はリストの長さを返す関数 length である．
# let rec length = function
# [] -> 0
# | _ :: rest -> 1 + length rest;;
val length : 'a list -> int = <fun>
length の型は _ パターンを使って先頭要素を使用してないことからわか
るように，どんなリストに対しても使うことができる．実際，型をみると
入力の要素型が型変数になっている．
# length [1; 2; 3];;
- : int = 3
# length [[true; false]; [false; false; false;]];;
- : int = 2
また length はふたつめの結果にみられるように，一番外側のリスト
の長さを計算するものである(結果は 5 ではない)．
append, reverse
次に示す append 関数はリスト同士を連結する関数である．append l1 l2 の
再帰的定義は
-
空リストに l2 を連結したものは l2 である．
- 先頭が v で，残りが l1'であるリストに
l を連結したものは，l1' と l の
連結の先頭に v を追加したものである．
と考えることができる．
# let rec append l1 l2 =
# match l1 with
# [] -> l2
# | x :: rest -> x :: (append rest l2);;
val append : 'a list -> 'a list -> 'a list = <fun>
# append [1; 2; 3] [4; 5; 6];;
- : int list = [1; 2; 3; 4; 5; 6]
この append の定義は，l1 の長さが長くなるほど
再帰呼び出しが深く行われ，l2 の長さには関係がない．
ちなみに append 関数は，もともと Objective Caml 起動時に中置オペレータ @ として
定義されている．
# [1; 2; 3] @ [4; 5; 6];;
- : int list = [1; 2; 3; 4; 5; 6]
また append を使ってリストを反転させる reverse 関数を定義できる．
# let rec reverse = function
# [] -> []
# | x :: rest -> append (reverse rest) [x];;
val reverse : 'a list -> 'a list = <fun>
リストの最後に要素を追加することは直接はできないので，一要素リストを作っ
て append している．しかし，この関数はあまり効率的ではない．なぜなら，
reverse の呼び出し一度につき，append が一度呼ばれるが，この時
append の第一引数の長さは「反転させようとする引数の長さ-1」であ
りappend を計算するのにその長さ分の計算量を必要とする．reverse の
再帰呼び出し回数は与えたリストの長さなので，リストの長さの自乗に比例し
た計算時間がかかってしまう．
これを改善したのが次の定義である．
# let rec revAppend l1 l2 =
# match l1 with
# [] -> l2
# | x :: rest -> revAppend rest (x :: l2)
# let rev x = revAppend x [];;
val revAppend : 'a list -> 'a list -> 'a list = <fun>
val rev : 'a list -> 'a list = <fun>
最初の再帰関数 revAppend が第一引数を先頭から順に l2 に追加して行く
関数である．先頭から追加していくため，l1 の順が逆になって
l2 に連結される．
# revAppend [1; 2; 3] [4; 5; 6];;
- : int list = [3; 2; 1; 4; 5; 6]
この関数も append と同じく，第一引数の長さだけに比例した時間がかかる．
リストの反転は revAppend の第二引数が空である特別な場合である．
# rev ['a'; 'b'; 'c'; 'd'];;
- : char list = ['d'; 'c'; 'b'; 'a']
map
map はリストの各要素に対して同じ関数を適用した結果のリストを求める
ための高階関数である．
# let rec map f = function
# [] -> []
# | x :: rest -> f x :: map f rest;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
たとえば，整数リストの各要素を2倍する式は map を使って，
# map (fun x -> x * 2) [4; 91; 0; -34];;
- : int list = [8; 182; 0; -68]
と書くことができる．map の型は今まで見た中でかなり複雑である．
まず，'a -> 'b で「何らかの関数」が第一引数であることがわかる．
カリー化関数とみるならば，第二引数は「何らかの関数」の定義域
の値を要素とするリストで，結果が「何らかの関数」の値域の値を
要素とするリストとなる．または「何らかの関数」を与えた時点で
リストからリストへの関数が返ってきていると解釈してもよい．
forall, exists
forall はリストの要素に関する述語(要素から bool への関数)と，リス
トをとり，全要素が述語を満たすかどうかを，exists は同様に述語と
リストをとって，述語を満たす要素があるかどうかを返す関数である．
# let rec forall p = function
# [] -> true
# | x :: rest -> if p x then forall p rest else false
# let rec exists p = function
# [] -> false
# | x :: rest -> (p x) or (exists p rest);;
val forall : ('a -> bool) -> 'a list -> bool = <fun>
val exists : ('a -> bool) -> 'a list -> bool = <fun>
# forall (fun c -> 'z' > c) ['A'; ' '; '+'];;
- : bool = true
# exists (fun x -> (x mod 7) = 0) [23; -98; 19; 53];;
- : bool = true
畳み込み関数 fold
上で見た sum_list, append はリストの要素すべてを用いた演算をするも
のである．実はこの二つの関数は共通の計算の構造を持っている．
sum_list は [i1; i2; ...; in], つまり
i1 :: i2 :: ... :: in :: []
から
i1 + (i2 + (... + (in + 0)...))
を計算し， append [e1; e2; ...; en] l2 は
e1 :: (e2 :: ... :: (en :: l2)...)
を計算している．
このふたつの計算の共通点は，
-
引数リストの cons を，sum_list では + で，append では ::
自身で置換え，
- 末尾の空リストも，sum_list では 0 で，append では l2 で
置換え，
- 右から演算を順次行っていく
ことである．このような「右から畳み込む」計算構造を一般化した高階関数を
fold_right と呼ぶ．逆に左から畳み込むのを fold_left と呼ぶ．
rev は fold_left の例である．何故なら，
rev [e1; e2; ...; en] は l ::: x を x :: l として，
(...(([] ::: e1) ::: e2) ... ::: en)
と表現できるからである．
以下が fold_right, fold_left の定義である．
fold_right f [e1; e2; ...; en] e f e1 (f e2 (... (f en e)...))
fold_left f e [e1; e2; ...; en] f (... (f (f e e1) e2) ...) en
を計算する．
# let rec fold_right f l e =
# match l with
# [] -> e
# | x :: rest -> f x (fold_right f rest e)
# let rec fold_left f e l =
# match l with
# [] -> e
# | x :: rest -> fold_left f (f e x) rest;;
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
# fold_right (fun x y -> x + y) [3; 5; 7] 0;;
- : int = 15
# fold_left (fun x y -> y :: x) [] [1; 2; 3];;
- : int list = [3; 2; 1]
fold_left, fold_right は要素はそのままで cons を適当な演算子に
読み替えて，計算をするものと思うことができる．一方，
map 関数はリストの構造はそのままで，要素だけを操作する
ような計算構造を抽象化した高階関数であった．実はリストに関する
再帰関数はほとんど map と fold_left または fold_right を組み合わせて
定義することができる．例えば，length は全要素をまず map を使って
1 に置換えて，足し算による畳み込みを行えばよいので，
# let length l = fold_right (fun x y -> x + y) (map (fun x -> 1) l) 0;;
val length : 'a list -> int = <fun>
と定義することも可能である．
連想リスト
辞書における見出しと説明文，データベースにおけるデータ検索のためのキー
とデータ，のような「関係」を表現するのに連想リスト(association list)
というデータ構造を用いる．連想リストは構造的にはペアのリストで表現される．
各要素 (a, b) はキー a の データ b への関連付けを表現する．
例えば，以下は，都市の名前をキー，市外局番をデータとした
連想リストの例である．
# let city_phone = [("Kyoto", "075"); ("Osaka", "06"); ("Tokyo", "03")];;
val city_phone : (string * string) list =
[("Kyoto", "075"); ("Osaka", "06"); ("Tokyo", "03")]
このような連想リストとキーから，関連づけられたデータを取り出す
関数 assoc は以下のように定義できる．
# let rec assoc a = function
# (a', b) :: rest -> if a = a' then b else assoc a rest;;
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
..................function
(a', b) :: rest -> if a = a' then b else assoc a rest..
val assoc : 'a -> ('a * 'b) list -> 'b = <fun>
# assoc "Osaka" city_phone;;
- : string = "06"
# assoc "Nara" city_phone;;
Exception: Match_failure ("", 124, 18).
連想リストにないキーで問い合わせを行うと，再帰呼び出しがリストの末端まで
到達した末にマッチングに失敗して例外を発生する．
| 5.4 |
Case Study: ソートアルゴリズム |
|
リストを使ったソートアルゴリズムをいくつかみていこう．以下では
リストを < に関する昇順(小さい方から順)に並べ替えることを考える．
(比較演算子 < は多相的であるため，ソート関数も多相的に使える．)
まずは準備として，ソートの対象として用いる，疑似乱数列を生成するため
の関数を定義する．
# let nextrand seed =
# let a = 16807.0 and m = 2147483647.0 in
# let t = a *. seed
# in t -. m *. floor (t /. m)
# let rec randlist n seed tail =
# if n = 0 then (seed, tail)
# else randlist (n - 1) (nextrand seed) (seed::tail);;
val nextrand : float -> float = <fun>
val randlist : int -> float -> float list -> float * float list = <fun>
# randlist 10 1.0 [];;
- : float * float list =
(2007237709.,
[1458777923.; 1457850878.; 101027544.; 470211272.; 1144108930.; 984943658.;
1622650073.; 282475249.; 16807.; 1.])
挿入ソート(insertion sort)は，既にソート済のリストに
新しい要素をひとつ付け加える操作を基本として，各要素を
順に付け加えていくものである．基本操作 insert は
# let rec insert (x : float) = function
# (* Assume the second argument is already sorted *)
# [] -> [x]
# | (y :: rest) as l -> if x < y then x :: l else y :: (insert x rest);;
val insert : float -> float list -> float list = <fun>
# insert 4.5 [2.2; 9.1];;
- : float list = [2.2; 4.5; 9.1]
と書くことができる．パターン中に出現する
⟨ パターン ⟩ as ⟨ 変数 ⟩
は as パターンと呼ばれるもので，パターンにマッチした値全体を
⟨ 変数 ⟩で参照できるものである．ここでは x :: y :: rest と
書く代りに x :: l としている．この insert を使ってソートを
行う関数は
# let rec insertion_sort = function
# [] -> []
# | x :: rest -> insert x (insertion_sort rest);;
val insertion_sort : float list -> float list = <fun>
と定義できる．
挿入ソートは insert, insertion_sort ともに入力に比例する回数の再帰呼出
しを行うため，計算には与えられたリストの長さの自乗に比例した時間がかかる．
クイックソート(quick sort)はC.A.R. Hoareが発明した効率の良いソー
トアルゴリズムで，分割統治(divide and conquer)法に基づき，下のよ
うな要領でソートを行う．
-
要素から適当にピボットと呼ばれる値を選びだす．
- 残りの要素をピボットに対する大小でふたつの集合に分割する．
- それぞれの部分集合にたいしてソートを行い，その結果を結合する．
# let rec quick = function
# [] -> []
# | [x] -> [x]
# | x :: xs -> (* x is the pivot *)
# let rec partition left right = function
# [] -> (quick left) @ (x :: quick right)
# | y :: ys -> if x < y then partition left (y :: right) ys
# else partition (y :: left) right ys
# in partition [] [] xs;;
val quick : 'a list -> 'a list = <fun>
この quick の定義は append を使用しているのでまだ効率の悪い点が
残っている．(append を使用しない定義は練習問題．) クイックソートは
リストの長さを n として，平均で nlogn に比例した時間で
行えることが知られている．
insert_sort (snd (randlist 10000 1.0 []))
と
quick (snd (randlist 10000 1.0 []))
を試してみよ．(snd はペアから第二要素を取り出す定義済の関数である．)
Exercise 1 次のうち，正しいリスト表現はどれか．コンパイラに入力する前に，
正しい場合と思う場合は式の型を，間違っていると思う場合はなぜ誤りか，
を予想してから実際に確認せよ．
-
[[]]
- [[1; 3]; ["hoge"]]
- [3] :: []
- 2 :: [3] :: []
- [] :: []
- [(fun x -> x); (fun b -> not b)]
Exercise 2
sum_list，max_list を，match を使わず null, hd, tl の
組合わせのみで定義せよ．match を使うテキストの定義と比べ，記述面
などの利害得失を議論せよ．
Exercise 3 次の関数を定義せよ．
-
正の整数 n から 0 までの整数の降順リストを生成する関数 downto0．
- 与えられた正の整数のローマ数字表現(文字列)を求める関数 roman．
(I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000 である．)
ただし，roman はローマ数字の定義も引数として受け取ることにする．
ローマ数字定義は，単位となる数とローマ数字表現の組を
大きいものから並べたリストで表現する．
例えば
roman [(1000, "M"); (500, "D"); (100, "C"); (50, "L");
(10, "X"); (5, "V"); (1, "I")] 1984
"MDCCCCLXXXIIII"
4, 9, 40, 90, 400, 900 などの表現にも注意して，
roman [(1000, "M"); (900, "CM"); (500, "D"); (400, "CD");
(100, "C"); (90, "XC"); (50, "L"); (40, "XL");
(10, "X"); (9, "IX"); (5, "V"); (4, "IV"); (1, "I")] 1984
"MCMLXXXIV"
となるようにせよ．
- 与えられたリストのリストに対し，内側のリストの要素を並べたリストを返
す関数 concat．
concat [[0; 3; 4]; [2]; [5; 0]; []] = [0; 3; 4; 2; 5; 0]
- 二つのリスト [a1; ...; an] と [b1; ...; bn] を引数として，
[(a1, b1); ...; (an, bn)] を返す関数 zip．(与えられたリストの長
さが異なる場合は長いリストの余った部分を捨ててよい．)
- リストと，リストの要素上の述語( bool 型を返す関数) p をとって，
p を満たす全ての要素のリストを返す関数 filter．
# let positive x = (x > 0);;
val positive : int -> bool = <fun>
# filter positive [-9; 0; 2; 5; -3];;
- : int list = [2; 5]
# filter (fun l -> length l = 3) [[1; 2; 3]; [4; 5]; [6; 7; 8]; [9]];;
- : int list list = [[1; 2; 3]; [6; 7; 8]]
- リストを集合とみなして，以下の集合演算をする関数を定義せよ．
-
belong a s で a が s の要素かどうかを判定する関数 belong．
- intersect s1 s2 で s1 と s2 の共通部分を返す関数 intersect．
- union s1 s2 で s1 と s2 の和を返す関数 union．
- diff s1 s2 で s1 と s2 の差を返す関数 diff．
但し，集合なので，要素は重複して現れてはならないことに気をつけよ．
(関数の引数には重複してないものが与えられるという仮定を置いてもよい．)
Exercise 4 f, g を適当な型の関数とする．
map f (map g l) を map を一度しか使用しない同じ意味の式
に書き換えよ．map (fun x -> ...) l の ... 部分は?
Exercise 5
forall, exists を fold_right, map を組み合わせて定義せよ．
Exercise 6
quick 関数を @ を使わないように書き換える．quicker
は未ソートのリスト l と，sorted というソート済でその要素の最小値
が l の要素の最大値より大きいようなリストを受け取る．
定義を完成させよ．
let rec quicker l sorted = ...
Exercise 7
与えられた自然数 r に対して x2 + y2 = r であるような，
(x,y) (ただし x ≥ y ≥ 0)の組を全てリストとして列挙する関
数 squares r を定義せよ．(検算用資料: r = 48612265 の時 32 個の解
があるそうです．)
Exercise 8
map の定義は末尾再帰的ではないため，入力リストの長さが長くなるとそれ
に比例した量のメモリ(スタック)が必要になる．map と同機能で，必要な
メモリ量が定数オーダーである map2 を定義せよ．(ヒント: 末尾再帰的
(iterative) な関数を使う．)