練習問題 5.2

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

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]