CSCI 330: Tuples and Higher-Order Functions

Goals

Overview

You have been tasked with implementing several functions in OCaml. All of the programs require relatively little coding ranging from 2 to 15 lines. If any function requires more than that, you will need to rethink your solution.

  1. Download the handout file from Autolab
  2. Update each of the functions with your own solutions. As a reminder, you are expected to complete this individually. Do not update any function headers
  3. Test your program using the OCaml environment installed on the Linux Lab machines
  4. Submit your updated handout file to the “Lab 3” Autolab assignment.

Start this assignment early I cannot emphasize this enough! ML programming is relatively easy (syntax-wise) but it will seem foreign, especially with recursion and list manipulation.

Note: Solutions using imperative features such as references, arrays, or while loops will receive no credit. Do not use any additional libraries, just use standard OCaml as installed in the Linux environment.

You are required to implement each of the following functions:

assoc (10 points)

Accepts a single parameter as a tuple of three values (d,k,l) where l is a list of key-value pairs [ (k1,v1) ; (k2,v2) ; ... ] and finds the first key which equals k. If such a key is found, then the value of that pair is returned. Otherwise, the default value d is returned. Your function should be tail recursive

Signature:

int * string * (string * int) list -> int

(* Or more general *)

'a * 'b * ('b * 'a) list -> 'a

Expected Output

assoc (-1,"jeff", [("sorin",85);("jeff",23);("moose",44)]);;

(* int = 23 *)


assoc (-1,"bob",[("mary",77);("bob",33);("bob",44)]);;

(* int = 33 *)


assoc (1337,"alice",[("bob",1);("charlie",2)]);;

(* int = 1337 *)

removeDuplicates (15 points)

Accepts a list, l, where we return the list of elements of l where all duplicates are removed and all remaining appear in the same order as in l. You should only replace the two occurences of failwith "to be written" in the existing skeleton. Do not change any of the other skeleton code. HINT: check out List.mem

Signature:

int list -> int list

(* generally: *)
'a list -> 'a list

Expected Output

removeDuplicates [1;6;2;4;12;2;13;6;9];;

(* int list = [1;6;2;4;12;13;9] *)

wwhile (15 points)

Without using any built-in OCaml functions (and definitely not the while or for construct, write an OCaml function, wwhile that takes as input a tuple (f,b) and calls the function f on input b to get a pair (b',c'). wwhile should continue calling f on b' to update the pair as long as c' is true. Once f returns a c' that is false, wwhile should return b'.

Your function should be tail recursive. Once you have implemented the function, you should get the following behavior at the OCaml prompt:

Signature:

(int -> int * bool) * int -> int

(* generally: *)
('a -> 'a * bool) * 'a -> 'a

Expected Output

let f x =
  let xx = x * x * x
  in (xx, xx < 100);;

wwhile (f, 2);;

(* int = 512 *)

In other words, the function parameter (f in the above example) needs to be a function that takes an int and returns a tuple with an int and a bool. wwhile is a function that takes a tuple – a function and an int. wwhile applies the provided function to the int and gets back an int * bool tuple. As long as the bool in the result is true, wwhile continues to recurse by using the new int result.

fixpoint (15 points)

Without using any built-in OCaml functions, modify the skeleton for fixpoint, which repeatedly updates b with f(b) until b = f(b) and then returns b. You should only replace the failwith "to be written" in the existing skeleton. Do not change any of the other skeleton code.

Once you have implemented the function, you should get the following behavior at the OCaml prompt:

Signature:

(int -> int) * int -> int

(* generally: *)
('a -> 'a) * 'a -> 'a)

Expected Output

let g x = truncate (1e6 *. cos (1e-6 *. float x));;
let h x = x * x;;

fixpoint (g,0);;
(* int = 739085 *)


fixpoint (h, 0);;
(* int = 0 *)

fixpoint (h, 1);;
(* int = 1 *)

In other words, fixpoint is using wwhile to find the value, x, of a function f where f(x) = x. To do this, you will need to write an anonymous function to pass in as part of the input to wwhile. In the first example above, the function being tested is g and the starting point for calling it is 0. g(739085) = 739085. This one is abstract and getting the pieces to fit together can be confusing, but it is essentially a one-liner.

Submission

Submit tuples.ml as the “Tuples” assignment through Autolab

Grading

70 points total

The comments for each function should have 1) a header description of the function, 2) the type signature, and 3) example input and output.

Attribution

This assignment was adapted from Sorin Lerner’s CSE 130 course at UCSD