(* Assignment 1: Introduction to Ocaml *)
(* Exercise 1.15, Problems 1-8 *)
(*
1. duple n x returns a list containing n copies of x
*)
let rec duple n x = match n with
0 -> []
| n -> x :: duple (n-1) x
(*
2. invert lst, where lst is a list of pairs, returns a list with
each pairs reversed
*)
let rec invert lst = match lst with
[] -> []
| ((a,b) :: lst') -> (b,a) :: invert lst'
(*
3. filter-in pred lst returns the list of those elements in lst
that satisfy the predicate pred
*)
let rec filter_in pred lst = match lst with
[] -> []
| (x::xs) -> if pred x
then x :: filter_in pred xs
else filter_in pred xs
(*
4. everyP pred lst returns true if every element of lst satisfies
pred, and returns false if any element fails to satisfy pred
*)
let rec everyP pred lst = match lst with
[] -> true
| (x::xs) -> pred x && everyP pred xs
(*
5. existP pred lst returns true if any element of lst satisfies
pred, and returns false if all elements fail to satisfy pred
*)
let rec existP pred lst = match lst with
[] -> false
| (x::xs) -> pred x || existP pred xs
(*
6. vector_index pred v returns the zero-based index of the first
element of v that satisfies the predicate pred. It raises an
exception if no element of v satisfies pred.
*)
exception Error
let vector_index pred v =
let len = Array.length v in
let rec loop i = (if i >= len
then raise Error
else if pred (v.(i))
then i
else loop (i+1))
in loop 0
(*
7. list_set lst n x returns a list like lst, except the nth element,
using zero-based indexing, is x. Raises an exception if lst is empty.
*)
let rec list_set lst n x = match lst with
[] -> raise Error
| (y :: ys) -> if n = 0
then x :: ys
else y :: list_set ys (n - 1) x
(*
8. product lst1 lst2 returns a list of pairs that represents the
cartesian product of lst1 and lst2.
*)
let rec product lst1 lst2 =
let rec loop x lst = match lst with
[] -> []
| (y :: ys) -> (x, y) :: loop x ys
in match lst1 with
[] -> []
| (x :: xs) -> List.append (loop x lst2) (product xs lst2)
(* accumulator version, just for practice *)
let rec product_acc lst1 lst2 =
let rec prod_acc ls1 acc =
let rec loop x lst = match lst with
[] -> acc
| (y :: ys) -> (x, y) :: loop x ys
in match ls1 with
[] -> acc
| (x :: xs) -> prod_acc xs (loop x lst2)
in prod_acc lst1 []