Objective Caml 入門 手習い（5章）その１

やっとリスト操作の章に入りました。5章は演習問題が多いので長くなりそうです。

• Objective Caml 入門

Exercise 2

問題

Exercise2 sum_list，max_list を，match を使わず null, hd, tl の 組合わせのみで定義せよ．match を使うテキストの定義と比べ，記述面 などの利害得失を議論せよ．

自分の答え

(* Exercise 2 *)
let hd (x::_) = x;;
let tl (_::xs) = xs;;

let null = function
  | [] -> true;
  | _ -> false;
;;

(* recursive *)
let rec sum_list_ l =
  match l with
  | [] -> 0
  | n::rest -> n + sum_list_ rest
;;

let rec sum_list l =
    if (null l) then 0
    else (hd l) + (sum_list (tl l))
;;

(* tail recursive *)
let rec sum_list2 s l =
  if (null l) then s
  else sum_list2 (s + (hd l)) (tl l)
;;

let sum_list2 = sum_list2 0;;

(* using fold *)
let sum_list' l = List.fold_left (+) 0 l;;

Exercise 3-1,2

問題

Exercise3 次の関数を定義せよ．
1. 正の整数 n から 0 までの整数の降順リストを生成する関数 downto0．
2. 与えられた正の整数のローマ数字表現(文字列)を求める関数 roman

自分の答え

(* Exercise 3-1 *)                                                              
                                                                                
let rec downto0 = function                                                      
  | 0 -> [0]                                                                    
  | n -> [n] @ downto0 (n-1)                                                    
;;                                                                              
                                                                                
let print_list l =                                                              
  begin                                                                         
    Printf.printf "[";                                                          
    List.map (Printf.printf "%d; ") l;                                          
    Printf.printf "]\n";                                                        
  end;                                                                          
;;                                                                              
                                                                                
print_list [];;                                                                 
print_list (downto0 10);;                                                       
Printf.printf "\n";;

(* Exercise 3-2 *)                                                              
let dict =                                                                      
  [(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")];;                                    
                                                                                
                                                                                
let rec rom_part_str rom_num = function                                         
  | 0 -> ""                                                                     
  | n -> rom_num ^ rom_part_str rom_num (n-1)                                   
;;                                                                              
                                                                                
                                                                                
let roman defdict num =                                                         
  let rec roman_part defdict' num' m str =                                      
    match (num', m) with                                                        
    | (0, 0) -> str                                                             
    | (_, _) ->                                                                 
        let (b, rc) = (hd defdict') in                                          
        let q = (m / b) in                                                      
        roman_part (tl defdict') q (m mod b) (str ^  (rom_part_str rc q))       
  in                                                                            
  roman_part defdict num num ""                                                 
;;                                                                              
                                                                                
Printf.printf "%s\n" (roman dict 10504);;

Exercise 3-3,4,5

問題

Exercise 3
3. 与えられたリストのリストに対し，内側のリストの要素を並べたリストを返 す関数 concat．
4. 二つのリスト [a1; ...; an] と [b1; ...; bn] を引数として， [(a1, b1); ...; (an, bn)] を返す関数 zip．(与えられたリストの長 さが異なる場合は長いリストの余った部分を捨ててよい．)
5. リストと，リストの要素上の述語( bool 型を返す関数) p をとって， p を満たす全ての要素のリストを返す関数 filter．

自分の答え

(* Exercise 3-3 *)                                                              
let concat = fold_left (@) [];;                                                 

print_list (concat [[1; 2; 3]; [2]; [4; 5;]; []]);;                             

(* Exercise 3-4 *)                                                              
let zip l1 l2 =
  let rec zip l1 l2 zipped =
    match (l1, l2) with
    | ([], _) | (_, []) -> zipped
    | (_, _) ->
        zip (List.tl l1) (List.tl l2) (zipped @ [(List.hd l1, List.hd l2)])
  in
  zip l1 l2 []
;;

(* Exercise 3-5 *)                                                              
let filter p l =
  let filter_elem e = if p e then [e] else [] in
  List.fold_left (@) [] (List.map filter_elem l)
;;