第１０章練習問題

gistfile1.ml

(* --- 10.1 --- *)
(* 答えをみた．else以降で引数のlstを使うという発想が出てこなかった *)
(* 目的：昇順に並んでいる lst の正しい位置に n を挿入する *) 
(* insert : int list -> int -> int list *) 
let rec insert lst n = match lst with 
    [] -> [n] 
  | first :: rest -> 
      if first < n then first :: ( insert rest n )
                    else n :: lst 

(* テスト *) 
let test1 = insert [] 3 = [3] 
let test2 = insert [1] 3 = [1; 3] 
let test3 = insert [3] 1 = [1; 3] 
let test4 = insert [1; 3; 4; 7; 8] 5 = [1; 3; 4; 5; 7; 8] 

(* --- 10.2 --- *)
(* これも答えをみた *)
(* 目的：昇順に並んでいる lst の正しい位置に n を挿入する *) 
(* insert : int list -> int -> int list *) 
let rec insert lst n = match lst with 
    [] -> [n] 
  | first :: rest -> 
      if first < n then first :: ( insert rest n )
                    else n :: lst 

(* 目的 : 整数のリストlstを受け取ったら，それを昇順に整列したリストを返す *)
(* ins_sort : int lst -> int lst *)
let rec ins_sort lst  = match lst with 
	[] -> []
    | first :: rest -> insert (ins_sort rest) first
(* 昇順に整列されている(ins_sort rest)にfirstの要素を挿入すると考える *)

(* テスト *)
let test1 = ins_sort []  = []
let test2 = ins_sort [1]  = [1]
let test3 = ins_sort [5; 3; 8; 1; 7; 4]  = [1; 3; 4; 5; 7; 8]

(* --- 10.3 ~ 10.12 --- *)
(* 飛ばす *)