118 lines
3.3 KiB
OCaml
118 lines
3.3 KiB
OCaml
(* 1. Write a function last : 'a list -> 'a option that returns the last
|
|
* element of a list. (easy) *)
|
|
let rec last xs =
|
|
match xs with
|
|
| [] -> None
|
|
| [x] -> Some(x)
|
|
| _ :: t -> last t
|
|
|
|
let () = assert(last ["a"; "b"; "c"; "d"] = Some("d"));;
|
|
let () = assert(last [] = None)
|
|
|
|
|
|
(* 2. Find the last but one (last and penultimate) elements of a
|
|
* list. (easy) *)
|
|
let rec last_two xs =
|
|
match xs with
|
|
| [] | [_] -> None
|
|
| [x; y] -> Some((x, y))
|
|
| _ :: t -> last_two t
|
|
|
|
let () = assert(last_two ["a"; "b"; "c"; "d"] = Some("c", "d"))
|
|
let () = assert(last_two ["a"] = None)
|
|
|
|
|
|
(* 3. Find the k'th element of a list. (easy) *)
|
|
let at k l =
|
|
let rec aux k n = function
|
|
| [] -> None
|
|
| h :: t when k < n -> None
|
|
| h :: t when k = n -> Some(x)
|
|
| h :: t when k > n -> aux k t (n+1) in
|
|
aux k l 1
|
|
|
|
let () = assert(at 3 [ "a" ; "b"; "c"; "d"; "e" ] = Some("c"))
|
|
let () = assert(at 3 [] = None)
|
|
|
|
|
|
(* 4. Find the number of elements of a list. (easy) *)
|
|
let length l =
|
|
let rec aux n = function
|
|
| [] -> 0
|
|
| _ :: t -> aux (n+1) t in
|
|
aux 0 l
|
|
|
|
|
|
let () = assert(length [ "a" ; "b" ; "c" ] = 3)
|
|
|
|
|
|
(* 5. Reverse a list. (easy) *)
|
|
let rev l =
|
|
let rec aux res = function
|
|
| [] -> res
|
|
| h :: t -> aux (h :: res) t in
|
|
aux [] l
|
|
|
|
let () = assert(rev [ "a" ; "b" ; "c" ] = ["c"; "b"; "a"])
|
|
|
|
|
|
(* 6. Find out whether a list is a palindrome. (easy) *)
|
|
let is_palindrome l =
|
|
rev l = l
|
|
|
|
let () = assert(is_palindrome [ "x" ; "a" ; "m" ; "a" ; "x" ])
|
|
let () = assert(not(is_palindrome [ "a" ; "b" ]))
|
|
|
|
(* type list 'a = [] | (::) of 'a * list 'a *)
|
|
|
|
(* 7. Flatten a nested list structure. (medium) *)
|
|
type 'a node =
|
|
| One of 'a
|
|
| Many of 'a node list
|
|
|
|
let flatten l =
|
|
let rec aux res = function
|
|
| [] -> res
|
|
| One x :: t -> aux (x :: res) t
|
|
| Many xs :: t -> aux (aux res xs) t in
|
|
List.rev (aux [] l)
|
|
|
|
let () = assert(flatten [ One "a" ; Many [ One "b" ; Many [ One "c" ; One "d" ] ; One "e" ] ] = ["a"; "b"; "c"; "d"; "e"])
|
|
|
|
(* 8. Eliminate consecutive duplicates of list elements. (medium) *)
|
|
(* TODO: check if tail recursive has same complexity as non-tail
|
|
recursive implementation? *)
|
|
let compress_tr l =
|
|
let rec aux acc prev = function
|
|
| [] -> acc
|
|
| h :: t when Some(h) = prev -> aux acc (Some h) t
|
|
| h :: t -> aux (h :: acc) (Some h) t in
|
|
List.rev (aux [] None l)
|
|
|
|
let rec compress l =
|
|
match l with
|
|
| [] | [_] -> l
|
|
| x :: y :: t -> if x = y then compress (y :: t)
|
|
else x :: (compress (y :: t))
|
|
|
|
let () = assert(compress ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"] = ["a"; "b"; "c"; "a"; "d"; "e"])
|
|
let () = assert(compress_tr ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"] = ["a"; "b"; "c"; "a"; "d"; "e"])
|
|
|
|
(* 9. Pack consecutive duplicates of list elements into
|
|
* sublists. (medium) *)
|
|
let pack l =
|
|
let rec aux ch acc = function
|
|
| [] -> acc
|
|
| h :: t -> if (Some h) = ch then aux ch ((h :: (List.hd acc)) :: List.tl acc) t
|
|
else aux (Some h) ([h] :: acc) t in
|
|
List.rev (aux None [] l)
|
|
|
|
(* 10. Run-length encoding of a list. (easy) *)
|
|
let encode l =
|
|
let rec aux ch count acc = function
|
|
| [] -> acc
|
|
| h :: t -> if h = ch then aux ch (count+1) acc t
|
|
else aux h 1 ((count, ch) :: acc) t in
|
|
match l with
|
|
| [] -> []
|
|
| h :: t -> List.rev (aux h 1 [] t)
|