流行りの関数型言語を勉強中(2)

挿入ソート

教科書の中の問題の解答。
例題をこなせば、それなりに作れるようになるようです。

(* 目的：あらかじめ昇順に並んでいる整数リスト(lst)と整数nを受け取ったら
 * 昇順となる位置にnを挿入したリストを返す関数 *)
(* insert: int -> int list -> int list *)
let rec insert n lst = match lst with
                [] -> [n]
                | first::rest -> if first >= n then  n :: first ::rest
                                 else first :: insert n rest (* rec *)

(* 目的：整数リスト(lst)を昇順にソートする(挿入ソート) *)
(* ins_sort int list -> int list *)
let rec ins_sort lst = match lst with
                [] -> []
                | first :: rest -> insert first (ins_sort rest) (* rec *)

(* テスト *)
let test1 = insert 1 [] = [1]
let test2 = insert 1 [0] = [0; 1]
let test3 = insert 3 [1; 2; 4; 5] = [1; 2; 3; 4; 5]
let test4 = insert 5 [1; 2; 3; 4] = [1; 2; 3; 4; 5]
let test5 = insert 5 [1; 10] = [1; 5; 10]
let test6 = insert 3 [1; 2; 3; 4] = [1; 2; 3; 3; 4]

let test7 = ins_sort [3; 1; 2] = [1; 2; 3]
let test8 = ins_sort [] = []
let test9 = ins_sort [5] = [5]
let test10 = ins_sort [5; 4; 3; 2; 1] = [1; 2; 3; 4; 5]
let test11 = ins_sort [1; 2; 4; 3] = [1; 2; 3; 4]