99 Problems in OCaml

OCaml-99-00.ml

(* 99 problems in OCaml: https://ocaml.org/learn/tutorials/99problems.html *)

OCaml-99-01.ml

(* Find the last element of a list *)

let rec last (a : 'a list) : 'a option = match a with
  | [] -> None
  | [x] -> Some x
  | _ :: t -> last t;;

(* for reference: val last : 'a list -> 'a option = <fun> *)

OCaml-99-02.ml

(* Find the last but one (last and penultimate) elements of a list. (easy) *)

let rec last_but_one (a : 'a list) : 'a option = match a with
  | [] -> None
  | [_] -> None
  | [x;_] -> Some x
  | _ :: t -> last_but_one t;;

(* For reference:  val last_but_one : 'a list -> 'a option = <fun> *)

OCaml-99-03.ml

(* Find the k'th element of a list. (easy) *)

let rec at (k : int) (xs : 'a list) : 'a option = match xs with
  | [] -> None
  | h :: t -> if k = 1 then Some h else at (k - 1) t;;

(* for reference: val at : int -> 'a list -> 'a option = <fun> *)

OCaml-99-04.ml

(* Find the number of elements of a list. (easy) *)
let length (xs : 'a list) : int =
  let rec reduce (i : int) (xs : 'a list) = match xs with
    | [] -> i
    | _ :: t -> reduce (i + 1) t
  in reduce 0 xs;;

(* for reference: val length : 'a list -> int = <fun> *)

OCaml-99-05.ml

(* Reverse a list. (easy) *)

let reverse (xs : 'a list) : 'a list =
  let rec reduce (rev : 'a list) (orig : 'a list) : 'a list = match orig with
    | [] -> rev
    | h :: t -> reduce (h :: rev) t
  in reduce [] xs;;

(* for reference: val reverse : 'a list -> 'a list = <fun> *)

OCaml-99-06.ml

(* Find out whether a list is a palindrome. (easy) *)

let palindrome (xs : 'a list) : bool = List.rev xs = xs;;

(* for reference: val palindrome : 'a list -> bool = <fun> *)

OCaml-99-07.ml

(* Flatten a nested list structure. (medium) *)

(* There is no nested list type in OCaml, so we need to define one
   first. A node of a nested list is either an element, or a list of
   nodes. *)
type 'a node =
  | One of 'a
  | Many of 'a node list;;

let flatten xs =
  let rec aux acc xs = match xs with
    | [] -> acc
    | One a :: t -> aux (a :: acc) t
    | Many l :: t -> aux (aux acc l) t
  in List.rev (aux [] xs);;

(* For reference: val flatten : 'a node list -> 'a list = <fun> *)

OCaml-99-08.ml

(* Eliminate consecutive duplicates of list elements. (medium) *)

let compress xs =
  let rec aux acc prev remain = match remain with
    | [] ->  prev :: acc
    | h :: t when (h = prev) -> aux acc h t
    | h :: t -> aux (prev :: acc) h t
  in match xs with
  | [] -> []
  | h :: t -> List.rev (aux [] h t);;

(* For reference: val compress : 'a list -> 'a list = <fun> *)

OCaml-99-09.ml

(* Pack consecutive duplicates of list elements into sublists. (medium) *)

let pack xs =
  let rec aux acc interim xs = match xs with
    | [] -> acc
    | h :: (n :: _ as t) when h = n -> aux acc (h :: interim) t
    | h :: t -> aux ((h :: interim) :: acc) [] t
  in List.rev (aux [] [] xs);;

(* For reference:
   val pack : 'a list -> 'a list list = <fun>
   pack ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"d";"e";"e";"e";"e"];;
   - : string list list =
   [["a"; "a"; "a"; "a"]; ["b"]; ["c"; "c"]; ["a"; "a"]; ["d"; "d"];
    ["e"; "e"; "e"; "e"]]
   *)

OCaml-99-10.ml

(* Run-length encoding of a list. (easy) *)

let encode xs =
  let rec aux acc count xs = match xs with
    | [] -> acc
    | h :: (next :: _ as t) when (h = next) -> aux acc (count + 1) t
    | h :: t -> aux ((h,count) :: acc) 1 t
  in List.rev (aux [] 1 xs);;

(*
   val encode : 'a list -> ('a * int) list = <fun>
   encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];;
   - : (string * int) list =
   [("e", 4); ("d", 1); ("a", 2); ("c", 2); ("b", 1); ("a", 4)]

*)

OCaml-99-11.ml

(* Modified run-length encoding. (easy) *)

type 'a rle =
  | One of 'a
  | Many of int * 'a;;

let encode xs =
  let rec aux acc count xs = match xs with
    | [] -> acc
    | h :: (next :: _ as t) when (h = next) -> aux acc (count + 1) t
    | h :: t when count = 1 -> aux ((One h) :: acc) 1 t
    | h :: t -> aux (Many (count, h) :: acc) 1 t
  in List.rev (aux [] 1 xs);;

(*

# encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];;
- : string rle list =
[Many (4, "a"); One "b"; Many (2, "c"); Many (2, "a"); One "d";
Many (4, "e")]

*)

OCaml-99-12.ml

(* Modified run-length encoding. (easy) *)

type 'a rle =
  | One of 'a
  | Many of int * 'a;;

let decode xs =
  let rec replicate i x xs =
    if (i = 0) then xs else replicate (i - 1) x (x :: xs)
  in let rec aux acc xs = match xs with
    | [] -> acc
    | (Many (i,a)) :: t -> aux (replicate i a acc) t
    | (One a) :: t -> aux (a :: acc) t
  in List.rev (aux [] xs);;

(*

# decode (encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"]);;
 - : string list =
 ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"]


# encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];;
 - : string rle list =
 [Many (4, "a"); One "b"; Many (2, "c"); Many (2, "a"); One "d";
 Many (4, "e")]

*)

OCaml-99-13.ml

(* Modified run-length encoding. (easy) *)

(* Note: 11.ml is supposed to use pack from 09, which I did not
         so this is just a copy of 10.
*)

type 'a rle =
  | One of 'a
  | Many of int * 'a;;

let encode xs =
  let rec aux acc count xs = match xs with
    | [] -> acc
    | h :: (next :: _ as t) when (h = next) -> aux acc (count + 1) t
    | h :: t when count = 1 -> aux ((One h) :: acc) 1 t
    | h :: t -> aux (Many (count, h) :: acc) 1 t
  in List.rev (aux [] 1 xs);;

(*

# encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];;
- : string rle list =
[Many (4, "a"); One "b"; Many (2, "c"); Many (2, "a"); One "d";
Many (4, "e")]

*)

OCaml-99-14.ml

(* Duplicate the elements of a list (easy) *)

let duplicate xs =
  let rec aux acc xs = match xs with
    | [] -> acc
    | h :: t -> aux (h :: h :: acc) t
  in List.rev (aux [] xs);;

(*

# let duplicate xs =
 let rec aux acc xs = match xs with
   | [] -> acc
   | h :: t -> aux (h :: h :: acc) t
in List.rev (aux [] xs);;
    val duplicate : 'a list -> 'a list = <fun>
# duplicate [1;2;3];;
- : int list = [1; 1; 2; 2; 3; 3]

*)

OCaml-99-15.ml

(* Replicate the leements of a list given number of times. (*medium*) *)

let replicate xs i =
  let rec prepend i x xs =
    if (i = 0) then xs else prepend (i - 1) x (x :: xs)
  in
  let rec aux acc xs i = match xs with
    | [] -> acc
    | h :: t -> aux (prepend i h acc) t i
  in List.rev (aux [] xs i);;

(*

# let replicate xs i =
  let rec prepend i x xs =
    if (i = 0) then xs else prepend (i - 1) x (x :: xs)
  in    
  let rec aux acc xs i = match xs with
    | [] -> acc
    | h :: t -> aux (prepend i h acc) t i
  in List.rev (aux [] xs i);;
              val replicate : 'a list -> int -> 'a list = <fun>
#

  ;;
# replicate ["a";"b";"c"] 3;;
- : string list = ["a"; "a"; "a"; "b"; "b"; "b"; "c"; "c"; "c"]

*)