Paradigms of Programming in O'Caml

Solutions of Exercises 1: Lists

1. Define the test whether a list is empty.

   (* 5 possibilities *)
   let empty = function l ->
      match l with
      | [] -> true
      | head::tail -> false;;
   
   let empty = function l ->
      match l with
      | [] -> true
      | _ -> false;;
   
   let empty l =
      match l with
      | [] -> true
      | _ -> false;;
   
   let empty l =
      if l = [] then true else false;;
   
   let empty = function | [] -> true | _ -> false;;
   

2. Define the length of a list.

   let rec length l = match l with
     | [] -> 0
     | head::tail -> 1+(length tail);;
   

3. Define Fibonacci sequence as a list of n elements.

   (* reversed variant *)
   let rec rfibseq n =
     if n <= 0 then [1]
     else
       if n = 1 then [1; 1]
       else
         let l = rfibseq (n-1) in
         match l with
           | a::b::tail -> (a+b)::l
   	| _ -> [];;
   
   let rec append l a =
     match l with
       | [] -> [a]
       | head::tail -> head::(append tail a);;
   
   let rec rev l =
     match l with
       | [] -> []
       | head::tail -> append (rev tail) head;;
   
   let fibseq n = rev (rfibseq n);;
   

4. Define the sum of all elements from a list.

   let rec sum l =
     match l with
       | [] -> 0
       | head::tail -> head + (sum tail);;
   

5. Define the sum of squares of all elements from a list.

   let rec sqsum l =
     match l with
       | [] -> 0
       | head::tail -> (head * head) + (sum tail);;
   

6. Define the collective operation on f-images of all elements from a list.

     let rec collective (op:'a -> 'a -> 'b) (f:'c -> 'a) (s:'b) (l:'c list) =
       match l with
         | [] -> s
         | head::tail -> op (f head) (collective op f s tail);;
   
    (* example *)
   
    let sqsum = collective (+) (fun x -> x*x) 0;;
   

7. Define the test whether in a list there is an element satisfying given condition

     let rec exists (cond:'a -> bool) (l: 'a list) =
       match l with
         | [] -> false
         | head::tail -> if cond head then true else exists cond tail;;
   
   (* example *)
   Random.init;;
   let rec gen k = if k <= 0 then [] else
   ((Random.int 1000)::(gen (k-1)));;
   let list = gen 1000;;
   if exists (fun x -> (20 < x) && (x <= 33)) list then print_string "found!\n";;
   

8. Define the test whether all elements of a list satisfy given condition

     let rec all (cond:'a -> bool) (l: 'a list) =
       match l with
         | [] -> true
         | head::tail -> if cond head then all cond tail else false;;
   

9. Insertion sort.
   see A Hundred Lines of Caml
10. Bubble sort.

    let rec bubblesort l =
      let (changed, y) = bubblestep l in
      if changed then bubblesort y
      else y
    and
      bubblestep l = match l with
        | [] -> (false, [])
        | [a] -> (false, [a])
        | a::b::t -> if a > b then (true, b::(snd (bubblestep (a::t))))
                     else let (changed, y) = bubblestep (b::t) in
    	              (changed, a::y);;
    

11. Selection sort.

    let rec selectionsort l =
      if l = [] then []
      else let (min, y) = selection l in min::(selectionsort y)
    and
      selection l = match l with
        | [] -> (0,[])
        | [a] -> (a, [])
        | h::t -> let (min, y) = selection t in
                  if min < h then (min, h::y) else (h, min::y);;