99 problems ocaml solutions

99probs.ml

(* Write a function last : 'a list -> 'a option that returns the last element of a list. *)
let rec last l = match l with
    [] -> None
  | [x] -> Some x
  | x :: l -> last l

(* Find the last but one (last and penultimate) elements of a list. *)
let rec last_two l = match l with
    [] -> None
  | [x] -> None
  | [x; y] -> Some (x, y)
  | x :: l -> last_two l

(* Find the k'th element of a list. *)
let rec at k l = match l with
    [] -> None
  | x :: l -> if k = 1 then Some x else at (k - 1) l

(* Find the number of elements of a list. *)
let length l = 
  let rec len l cur = match l with
      [] -> cur
    | x :: xs -> len xs (cur + 1)
  in len l 0


(* Reverse a list. *)
let rev l = 
  let rec rec_rev l cur = match l with
      [] -> cur
    | x :: xs -> rec_rev xs (x :: cur)
  in rec_rev l []


(* Find out whether a list is a palindrome. *)
let is_palindrome l = l = (rev l)

type 'a node = 
  One of 'a
| Many of 'a node list

let rec flatten l = match l with 
    [] -> []
  | x :: xs -> 
    match x with 
      One (y) -> y :: flatten xs
    | Many ys -> flatten ys @ flatten xs
    
(* Eliminate consecutive duplicates of list elements. *)
let compress l =
  let rec aux l cur rl = match l with
      [] -> rl
    | x :: xs ->
      if rl = [] or x != cur then aux xs x (rl @ [x])
      else aux xs cur rl
  in aux l (List.hd l) [];;

let rec compress = function
  | a :: (b :: _ as t) -> if a = b then compress t else a :: compress t
  | smaller -> smaller;;

(* Pack consecutive duplicates of list elements into sublists. *)
let pack l =
  let rec aux current acc = function
    | [] -> []
    | [x] -> (x :: current) :: acc
    | x :: (y :: _ as t) ->
      if x = y then aux (x :: current) acc t
      else aux [] ((x :: current) :: acc) t
  in List.rev (aux [] [] l);;

(* Run-length encoding of a list. *)
let encode list = 
  let rec aux current acc = function
    | [] -> []
    | [x] -> (acc + 1, x) :: current
    | x :: (y :: _ as t) ->
      if x = y then aux current (acc + 1) t
      else aux ((acc + 1, x) :: current) 0 t
  in List.rev (aux [] 0 list);;

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

let encode list = 
  let rec aux = function
    | [] -> []
    | [] :: t -> aux t
    | [x] :: t -> One x :: aux t
    | (x :: l) :: t -> Many (1 + List.length l, x) :: aux t in
  aux (pack list);;

(* Decode a run-length encoded list. *)