月: 2008年1月

次の関数を定義しなさい。

1. 正の整数 n から 1 までの整数の降順リストを生成する関数 downto1。

# let rec downto1 n = if n = 0 then [] else n :: downto1 (n-1);;
val downto1 : int -> int list = <fun>
# downto1 6;;
- : int list = [6; 5; 4; 3; 2; 1]

2. 与えられた正の整数のローマ数字表現を求める関数 roman。ただし，roman は単位となる 数とローマ数字表現の組を大きいものから並べたリストで表現した，ローマ数字の定義も引 数として受け取ることにする。

# let roman r n =
let rec iter_string n s = if n = 0 then "" else s ^ iter_string (n-1) s in
let roman' num rom =
let (n, s) = num in
let (rn, rs) = rom in
(n mod rn, s ^ iter_string (n / rn) rs)
in
snd (List.fold_left roman' (n, "") r)
;;
val roman : (int * string) list -> int -> string = <fun>
# roman [(1000,"M");(500,"D");(100,"C");(50,"L");(10,"X");(5,"V");(1,"I")] 1984;;
- : string = "MDCCCCLXXXIIII"

また，900，400，90，40，9，4 の表現を変えると

# roman [(1000,"M");(900,"CM");(500,"D");(400,"CD");(100,"C");(90,"XC");(50,"L");(4 0,"XL");(10,"X");(9,"IX");(5,"V");(4,"IV");(1,"I")] 1984;;
- : string = "MCMLXXXIV"

3. 与えられたリストのリストに対し，（内側のリストの）要素の総数を返す関数 nested_le ngth。

# let nested_length l = List.length (List.concat l);;
val nested_length : 'a list list -> int = <fun>
# nested_length [[1;2;3]; [4;5]; [6]; [7;8;9;10]];;
- : int = 10
# nested_length [[1;2;3]; [4;5]; []; [6;7;8;9]];;
- : int = 9

次の 4. を見て気がついた。もしかして List.concat は使っちゃだめだったのか？

# let nested_length l = List.fold_left (fun x y -> x + List.length y) 0 l;;
val nested_length : 'a list list -> int = <fun>
# nested_length [[1;2;3]; [4;5]; [6]; [7;8;9;10]];;
- : int = 10

4. 与えられたリストのリストに対し，内側のリストの要素を並べたリストを返す関数 concat。

# let concat l = List.fold_left (fun x y -> x @ y) [] l;;
val concat : '_a list list -> '_a list = <fun>
# concat [[1;2;3];[4;5];[6];[7;8;9;10]];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

もしかして List.fold_left も使わないのかな。なら再帰で。

# let rec concat' = function
[] -> []
| hd::tl -> hd @ concat' tl
;;
val concat' : 'a list list -> 'a list = <fun>
# concat' [[1;2;3]; [4;5]; [6]; [7;8;9;10]];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

Haskell で一番有名（？）なコードを OCaml で書いてみた。

# let rec qsort = function
[] -> []
| hd::tl -> qsort (List.filter (fun x -> x < hd) tl) @ [hd] @ qsort (List.filter  (fun y -> hd <= y) tl)
;;
val qsort : 'a list -> 'a list = <fun>
# qsort [1;5;3;2;6;7;4;9];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 9]

はじめ List.filter に与える関数を (>hd) みたいに書いたらだめだった。 OCaml ではセクションは使えないらしい。演算子を関数的に使って部分適用ならok。

# let rec qsort' = function
[] -> []
| hd::tl -> qsort' (List.filter ((>) hd) tl) @ [hd] @ qsort' (List.filter ((<=) hd) tl)
;;
val qsort' : 'a list -> 'a list = <fun>
# qsort' [1;5;3;2;6;7;4;9];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 9]

パターンに条件を付加するのがガード。

# let abs' = function
0 -> 0
| n when n > 0 -> n
| n -> (-1) * n
;;
val abs' : int -> int = <fun>

2番目の when n > 0 がガード。パターンは3番目と同じだけどここで条件分けをしている。3番目のパターンは条件が付いていないので残りの場合（n < 0 の場合）にマッチする。

# abs' (-1);;
- : int = 1
# abs' 8;;
- : int = 8
# abs 0;;
- : int = 0

3番目のパターンにもガードをつけると警告がでる。

# let abs'' = function
0 -> 0
| n when n > 0 -> n
| n when n < 0 -> (-1) * n
;;
Characters 12-82:
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
1
(However, some guarded clause may match this value.)
............function
0 -> 0
| n when n > 0 -> n
| n when n < 0 -> (-1) * n
val abs'' : int -> int = <fun>

パターンマッチングが網羅的でないといっている。要するにどのパターンにもマッチしない可能性があるというわけだ。

これは， when の条件は false に可能性がある，という見積もりをするせい。そのため，上に書いたような警告がでる。最初のコードでは3番目のパターンには条件が付いていないから，n がどんな値でもマッチすることになり，警告もでない。

タプルにしてしまえばいい。ただし，function構文はつかえない。

# let rec zip l r =
match (l, r) with
([], _) -> []
| (_, []) -> []
| (h1::t1, h2::t2) -> (h1, h2) :: zip t1 t2
;;
val zip : 'a list -> 'b list -> ('a * 'b) list = <fun>
# zip [1;2;3;4] ['a';'b';'c'];;
- : (int * char) list = [(1, 'a'); (2, 'b'); (3, 'c')]

パターンの中の _ はワイルドカード。

match式によるパターンマッチを function構文で書くことができる。パターンマッチのための仮引数が現れないのがミソ。

# let rec sum_list = function
[] -> 0
| hd::tl -> hd + sum_list tl
;;
val sum_list : int list -> int = <fun>
# sum_list [1;2;3;4;5;6;7;8;9;10];;
- : int = 55

List.map はリストの各要素に関数を適用する。

# List.map (fun x -> x * x) [1;2;3;4;5];;
- : int list = [1; 4; 9; 16; 25]

実装してみる。

# let rec map' f l =
match l with
[] -> []
| hd::tl -> f hd :: map' f tl
;;
val map' : ('a -> 'b) -> 'a list -> 'b list = <fun>
# map' (fun x -> x * 10) [1;2;3;4;5];;
- : int list = [10; 20; 30; 40; 50]

function構文を使って，

# let rec map'' f = function
[] -> []
| hd::tl -> f hd :: map'' f tl
;;
val map'' : ('a -> 'b) -> 'a list -> 'b list = <fun>
# map'' (fun x -> x * 10) [1;2;3;4;5];;
- : int list = [10; 20; 30; 40; 50]

List.fold_left は左から，List.fold_right は右からたたみ込む。

# List.fold_left (fun x y -> "(" ^ x ^ "," ^ y ^ ")") "A" ["B";"C";"D"];;
- : string = "(((A,B),C),D)"
# List.fold_right (fun x y -> "(" ^ x ^ "," ^ y ^ ")") ["A";"B";"C"] "D";;
- : string = "(A,(B,(C,D)))"

引数の順番が違うので，ちょっと注意が必要。

# List.fold_left;;
- : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
# List.fold_right;;
- : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>

あいだが開いてしまった。多相や型推論の部分はどうにも頭の整理できないので，先に進もう。

リストは全体を [ と ] で囲って，要素を ; で区切る。[]は空リストを表す。

# [1;2;3];;
- : int list = [1; 2; 3]
# [];;
- : 'a list = []
||<
::（コンスオペレーター）で要素をリストの先頭に追加する。
>||
# 1 :: [2;3;4;5];;
- : int list = [1; 2; 3; 4; 5]

引数のパターンマッチには match式をつかう。リストパターンは :: を使える。たとえば：

# let rec sum l =
match l with
[] -> 0
| hd::tl -> hd + sum tl
;;
val sum : int list -> int = <fun>
# sum [1;3;5;7;9];;
- : int = 25

List.length はリストの長さを返す。

# List.length [1;2;3;4;5];;
- : int = 5

実装してみる。

# List.length [1;2;3;4;5];;
- : int = 5
# let rec length' l =
match l with
[] -> 0
| hd :: tl -> 1 + length' tl
;;
val length' : 'a list -> int = <fun>
# length' [1;2;3;4;5];;
- : int = 5