1. [[]] 'a list list
2. [[1;3]; ["hoge"]] NG
3. [3] :: [] int list list
4. 2 :: [3] :: [] NG 左からみてくと一見良さそうだけど,:: が右結合なので int list list に int をpush_frontしようとしている事になってしまう. (2 :: [3]):: [] ならOK
5. [] :: [] 'a list list
6. [(fun x -> x) ; (fun b -> not b) ] (bool -> bool) list
fold_leftを使ったもの。引数なしで定義すると…。
let concat = List.fold_left (@) [];;
この時のコンパイラの出力。
# val concat : '_a list list -> '_a list = <fun>
'_aに関しては第3回のページを参照。 これはOCamlの参照という機能を使えるようにするための制限だとか。 実際に引数を与えると型が固定される。
# concat [[1;2];[3;4]];; - : int list = [1; 2; 3; 4] # concat;; - : int list list -> int list = <fun> #
多相性を持たせるには引数を付ければよい。
let concat list = List.fold_left (@) [] list;;
同じく、この時のコンパイラの出力。
val concat : 'a list list -> 'a list = <fun>
let rec zip s1 s2 = match s1 with [] -> [] | x::xs -> match s2 with [] -> [] | y::ys -> (x,y) :: zip xs ys;;
matchに組を使うと見やすくなる。(括弧はいらないとのこと。)
let rec zip' s1 s2 = match s1,s2 with [],_ -> [] | _,[] -> [] | x::xs,y::ys -> (x,y) :: zip' xs ys;;
let rec belong a s = match s with [] -> false | x::xs -> if x = a then true else belong a xs
問題文をそのまま書いたもの。
let rec intersect s1 s2 = match s1 with [] -> [] | x::xs -> if belong x s2 then x :: intersect xs s2 else intersect xs s2;;
filterを使ったもの。
let intersect' s1 s2 = filter (fun x -> belong x s1) s2;;
問題文をそのまま書いたもの。
let rec union s1 s2 = match s1 with [] -> s2 | x::xs -> if belong x s2 then union xs s2 else x :: (union xs s2);;
filterを使ったもの。
let union' s1 s2 = s1 @ filter (fun x -> not (belong x s1)) s2;;
問題文をそのまま書いたもの。
let rec diff s1 s2 = match s1 with [] -> [] | x::xs -> if belong x s2 then diff xs s2 else x :: diff xs s2;;
filterを使ったもの。
let diff' s1 s2 = filter (fun x -> not (belong x s2)) s1;;
let forall' prop l = fold_right (&&) (map prop l) true let exists' prop l = fold_right (||) (map prop l) false
↑fold_rightとmapを使った方法。(問題にはfold_rightとmapを使えと書いてあった。) しかしこれだとリストlを何度もみながら計算するので効率がいいとはいえない。 ↓は小笠原さんによる改良versionである。(違ったら指摘してください。)
let forall'' prop l = fold_right (fun x b -> b && prop x) l true let exists'' prop l = fold_right (fun x b -> b || prop x) l false