Sections

Due: Wednesday, October 17 at 4:00pm
Submission cutoff: Saturday, October 20 at 4:00pm

In this assignment, you will implement modules for a few polymorphic data structures in OCaml and the typed lambda calculus. You will gain experience with advanced OCaml features (higher order functions, user defined types, recursive data structures) and understand their theoretical analogs.

1: List (40%)

Recall from class the venerable linked list, represented in OCaml by the recursive type Nil | Cons of 'a * 'a list. Your task is to implement the functions on the List2 type signature:

module type List2 = sig
  type 'a list = Nil | Cons of 'a * 'a list

  val foldr : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b
  val map : ('a -> 'b) -> 'a list -> 'b list
  val filter : ('a -> bool) -> 'a list -> 'a list
  val reduce : ('a -> 'a -> 'a) -> 'a list -> 'a option
  val combine_keys : ('a * 'b) list -> ('a * ('b list)) list
  val to_string : ('a -> string) -> 'a list -> string
end

With the exception of foldr, every function must not be defined recursively, or with recursive helper functions. (Hint: define every function in terms of foldr.)

  1. foldr : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b

    Foldr, or “fold right”, is a function that iterates over a list and repeatedly applies a function on each element, accumulating a piece of state along the way. Foldr defines the most generic way to iterate over the list data structure. For example:

    let f = fun x acc -> x + acc in
foldr f 0 (Cons(1, Cons(2, Cons(3, Nil)))) = f 1 (f 2 (f 3 0))     (* evaluates to 6 *)

  2. map : ('a -> 'b) -> 'a list -> 'b list

    Map applies the input function to each element of the list.

    map (fun x -> x + 1) (Cons(1, Nil)) = Cons(2, Nil)

  3. filter : ('a -> bool) -> 'a list -> 'a list

    Filter takes a predicate, or function from a list element to a boolean, and returns a new list with only the elements for which the predicate is true.

    filter (fun x -> x mod 2 = 0) (Cons(1, Cons(2, Nil))) = Cons(2, Nil)

  4. reduce : ('a -> 'a -> 'a) -> 'a list -> 'a option

    Reduce takes a function that combines adjacent elements, and reduces the list down to a single element. Reduce returns None if the input list is empty.

    reduce (+) (Cons(1, Cons(2, Nil))) = Some(3)

  5. combine_keys : ('a * 'b) list -> ('a * ('b list)) list

    This function takes a list of (key, value) pairs, matches up pairs with identical keys, and combines their values into a list.

    combine_keys (Cons(("a", 1), Cons(("a", 2), Cons(("b", 1), Nil)))) =
  Cons(("a", Cons(1, Cons(2, Nil))), Cons(("b", Cons(1, Nil)), Nil))

  6. to_string : ('a -> string) -> 'a list -> string

    This function takes a function that converts list elements to strings, and then turns the entire list into a string.

    to_string string_of_int (Cons(1, Cons(2, Nil))) = "1 2 "

2: Stream (40%)

Your next task is to implement an infinite data type, that of streams. A stream is essentially an iterator that always returns a value.

module type Stream2 = sig
  type 'a stream = Stream of (unit -> 'a * 'a stream)
  val head : 'a stream -> 'a
  val tail : 'a stream -> 'a stream
  val take : 'a stream -> int -> 'a list * 'a stream
  val zip : 'a stream -> 'b stream -> ('a * 'b) stream
  val enumerate : 'a stream -> (int * 'a) stream
  val windows : 'a stream -> int -> ('a list) stream
end

Read the type definition carefully. Because OCaml does not support recursive types outside of variants, we represent streams as a variant with one branch. The type of a stream is unit -> 'a * 'a stream, or a function that produces both a value and a resultant stream when called. For example, here’s a stream that always produces the same value:

let rec repeat (n : int) : int stream =
  Stream (fun () -> (n, repeat (n)))

  1. head : 'a stream -> 'a

    Head returns the current/first element in the stream.

    let s = repeat 1 in
(head s) = 1

  2. tail : 'a stream -> 'a stream

    Tail returns the stream starting at the next element.

    let s = repeat 1 in
let s = tail s in
(head s) = 1

  3. take : 'a stream -> int -> 'a list * 'a stream

    Take removes the first elements from a stream, returning those elements and the remaining stream.

    let s = repeat 1 in
let (l, s) = (take s 3) in
l = Cons(1, Cons(1, Cons(1, Nil)))

  4. zip : 'a stream -> 'b stream -> ('a * 'b) stream

    Zip takes two streams and produces a new stream of pairs of their items.

    let s = zip (repeat 1) (repeat 2) in
(head s) = (1, 2)

  5. enumerate : 'a stream -> (int * 'a) stream

    Enumerate takes a stream and returns a new stream where each item is indexed from 0 to infinity.

    let s = enumerate (repeat 1) in
(head s) = (0, 1) && (head (tail s)) = (1, 1)

  6. windows : 'a stream -> int -> ('a list) stream

    Windows takes a stream and produces a new stream of fixed size sliding windows over the input stream.

     let s = windows (enumerate (repeat 1)) 2 in
 (head s) = Cons((0, 1), Cons((1, 1), Nil))

Additionally, you must implement the two stream test functions in StreamTests of upfrom and fib.

  1. upfrom : int -> int stream

    This function takes a number n, and returns a stream that counts to infinity by 1 starting at n.

  2. fib : unit -> int stream

    This function creates a stream of the Fibonacci numbers.

3: Stream calculus (20%)

Lastly, you’re going to translate a subset of your OCaml solutions to part 2 into the typed lambda calculus. Using the semantics for fixpoints, recursive types, and polymorphic types as presented this past week, implement the functions for tail, enumerate, and upfrom with the same semantics as above.

For example, the implementation of head is:

A few hints:

  • Remember that the typed lambda calculus is more explicit than OCaml. Don’t forget your necessary folds/unfolds and type functions/type function applications.
  • You will need to use the fix operator to emulate let rec.
  • In our solution, the implementation logic did not change between OCaml and lambda calculus, just the type machinery around recursive/polymorphic types.

Submission

To submit your work, we have two Gradescope assignments for the written and programming sections. For the written section, upload your assign3.pdf file. For the programming section, upload your list2.ml and stream2.ml files.