Training OCaml

training.ml

#use "topfind";;
#thread;;

(* Input from file *)
let input_file filename =
  let file = open_in filename in
  let rec input_lines result =
    match input_line file with
      | line -> input_lines (line :: result)
      | exception _ ->
        close_in file;
        List.rev result
  in

  input_lines []
;;

(*
List.iter (fun v -> print_endline v) (input_file "./training.ml");;
*)


(* Range *)
let range first last =
  let rec generate result current =
    if current < last then
      generate (current :: result) (current + 1)
    else
      List.rev result
  in

  generate [] first
;;

(*
print_endline (string_of_int (List.length (range 0 1000000)));;
List.iter (fun v -> print_endline (string_of_int v)) (range 0 10);;
*)


(* Take *)
let take items count =
  let rec pick result current = function
    | [] -> List.rev result
    | hd :: tl ->
      if current > 0 then
        pick (hd :: result) (current - 1) tl
      else
        List.rev result
  in

  pick [] count items
;;

(*
print_endline (string_of_int (List.length (take (range 0 1000000) 750000)));;
List.iter (fun v -> print_endline (string_of_int v)) (take (range 0 10) 5);;
*)

(* Drop *)
let drop items count =
  let rec pick result current = function
    | [] -> List.rev result
    | hd :: tl as items ->
      if current > 0 then
        pick result (current - 1) tl
      else
        items
  in

  pick [] count items
;;

(*
print_endline (string_of_int (List.length (drop (range 0 1000000) 250000)));;
List.iter (fun v -> print_endline (string_of_int v)) (drop (range 0 10) 5);;
*)

(* Slice *)
let slice items first last =
  take (drop items first) (last - first)
;;

(*
print_endline (string_of_int (List.length (slice (range 0 1000000) 150000 900000)));;
List.iter (fun v -> print_endline (string_of_int v)) (slice (range 0 10) 2 7);;
*)

let partition items pivot =
  let rec split result1 result2 = function
    | [] -> (List.rev result1, List.rev result2)
    | hd :: tl ->
      if hd < pivot then
        split (hd :: result1) result2 tl
      else
        split result1 (hd :: result2) tl
  in

  split [] [] items
;;

(*
let items1, items2 = partition (range 0 1000000) 500000;;
print_endline (string_of_int (List.length items1));;
print_endline (string_of_int (List.length items2));;

let items3, items4 = partition (range 0 10) 5;;
List.iter (fun v -> print_endline (string_of_int v)) items3;;
print_endline "-";;
List.iter (fun v -> print_endline (string_of_int v)) items4;;
*)

let concat items1 items2 =
  let rec assign result items1 items2 =
    match items1, items2 with
      | [], [] -> List.rev result
      | [], hd :: tl -> assign (hd :: result) items1 tl
      | hd :: tl, _ ->
        assign (hd :: result) tl items2
  in

  assign [] items1 items2
;;

(*
let items1, items2 = partition (range 0 1000000) 500000;;
print_endline (string_of_int (List.length (concat items1 items2)));;

let items3, items4 = partition (range 0 10) 5;;
List.iter (fun v -> print_endline (string_of_int v)) (concat items3 items4);;
*)

let rec qsort = function
  | [] -> []
  | hd :: tl ->
    let items1, items2 = partition tl hd in
    concat (qsort items1) (hd :: (qsort items2))
;;

(*
Random.self_init ();;
let random = List.sort (fun a b -> (Random.int 3) - 1) (range 0 10);;
List.iter (fun v -> print_endline (string_of_int v)) random;;
print_endline "-";;
List.iter (fun v -> print_endline (string_of_int v)) (qsort random);;
*)


let merge items1 items2 =
  let rec assign result items1 items2 =
    match items1, items2 with
      | [], [] -> List.rev result
      | [], hd :: tl ->
        assign (hd :: result) items1 tl
      | hd :: tl, [] ->
        assign (hd :: result) tl items2
      | hd1 :: tl1, hd2 :: tl2 ->
        if hd1 < hd2 then
          assign (hd1 :: result) tl1 items2
        else
          assign (hd2 :: result) items1 tl2
  in

  assign [] items1 items2
;;

(*
let items1, items2 = partition (range 0 1000000) 500000;;
print_endline (string_of_int (List.length (merge items1 items2)));;

let items3, items4 = partition (range 0 10) 5;;
List.iter (fun v -> print_endline (string_of_int v)) (merge items3 items4);;
*)


let split items =
  let count = List.length items / 2 in
  let rec partition result1 result2 current = function
    | [] -> (List.rev result1, List.rev result2)
    | hd :: tl ->
      if current > 0 then
        partition (hd :: result1) result2 (current - 1) tl
      else
        partition result1 (hd :: result2) (current - 1) tl
  in

  partition [] [] count items
;;

(*
let items1, items2 = split (range 0 1000000);;
print_endline (string_of_int (List.length items1));;
print_endline (string_of_int (List.length items2));;

let items3, items4 = split (range 0 10);;
List.iter (fun v -> print_endline (string_of_int v)) items3;;
print_endline "-";;
List.iter (fun v -> print_endline (string_of_int v)) items4;;
*)


let rec msort = function
  | [] -> []
  | [_] as item -> item
  | items ->
    let items1, items2 = split items in
    merge (msort items1) (msort items2)
;;

(*
Random.self_init ();;
let random = List.sort (fun a b -> (Random.int 3) - 1) (range 0 10);;
List.iter (fun v -> print_endline (string_of_int v)) random;;
print_endline "-";;
List.iter (fun v -> print_endline (string_of_int v)) (msort random);;
*)