In this recitation, we will see more examples of modules that implement functional data structures.
In Recitation 7, we discussed stacks and queues. We repeat the interface for stacks here, adding a notation for representing the abstract contents.
module type STACK =
sig
(* Overview: an 'a stack is a stack of elements of type 'a.
* We write |e1, e2, ... en| to denote the stack with e1
* on the top and en on the bottom. *)
type 'a stack
exception EmptyStack
val empty : 'a stack
val isEmpty : 'a stack -> bool
val push : ('a * 'a stack) -> 'a stack
val pop : 'a stack -> 'a stack
val top : 'a stack -> 'a
val map : ('a -> 'b) -> 'a stack -> 'b stack
val app : ('a -> unit) -> 'a stack -> unit
(* note: app traverses from top of stack down *)
end
Now we present an interface for queues; first-in, first-out data structures. Again, we introduce a notation for discussing the abstract contents of the queue.
module type QUEUE =
sig
(* Overview: an 'a queue is a FIFO queue of elements of type 'a.
* We write <e1, e2, ... en> to denote the queue whose front
* is e1 and whose back is en. Elements are enqueued at the back
* and dequeued from the front. *)
type 'a queue
exception EmptyQueue
val empty : 'a queue
val isEmpty : 'a queue -> bool
(* enqueue(x, q) is q with x enqueued at the back.
* Example: enqueue(3, <1,2>) = <1,2,3> *)
val enqueue : ('a * 'a queue) -> 'a queue
(* dequeue(q) is q with its front element removed.
* Requires: q is nonempty. *).
val dequeue : 'a queue -> 'a queue
(* front(q) is the element at the front. Requires: q is nonempty. *)
val front : 'a queue -> 'a
val map : ('a -> 'b) -> 'a queue -> 'b queue
val app : ('a -> unit) -> 'a queue -> unit
end
The simplest possible implementation for queues is to represent a queue via two stacks: one stack A on which to enqueue elements, and one stack B from which to dequeue elements. When dequeuing, if stack B is empty, then we reverse stack A and consider it the new stack B.
Here is an implementation for such queues. It uses the stack structure Stack, which is rebound to the name S inside the structure to avoid long identifier names.
module Queue : QUEUE =
struct
module S = Stack
type 'a queue = ('a S.stack * 'a S.stack)
(* AF: The pair (|e1, e2, ... en|, |e'1, e'2, ..., e'n|) represents
* the queue <e'1, e'2, ..., e'n, en, ..., e2, e1>.
*)
exception EmptyQueue
let empty : 'a queue = (S.empty, S.empty)
let isEmpty ((s1,s2):'a queue) =
S.isEmpty (s1) && S.isEmpty (s2)
let enqueue (x:'a, (s1,s2):'a queue) : 'a queue =
(S.push (x,s1), s2)
let rev (s:'a S.stack):'a S.stack = let
let loop (old:'a S.stack, new:'a S.stack):'a S.stack =
if (S.isEmpty (old))
then new
else loop (S.pop (old), S.push (S.top (old),new))
in
loop (s,S.empty)
let dequeue ((s1,s2):'a queue) : 'a queue =
if (S.isEmpty (s2))
then try (S.empty, S.pop (rev (s1)))
with S.EmptyStack -> raise EmptyQueue
else (s1,S.pop (s2))
let front ((s1,s2):'a queue):'a =
if (S.isEmpty (s2))
then try S.top (rev (s1))
with S.EmptyStack -> raise EmptyQueue
else S.top (s2)
let map (f:'a -> 'b) ((s1,s2):'a queue):'b queue =
(S.map f s1, S.map f s2)
let app (f:'a -> unit) ((s1,s2):'a queue):unit =
(S.app f s2;
S.app f (rev (s1)))
end
Another simple data type is a fraction, a ratio of two integers. Here is a possible interface:
module type FRACTION =
sig
(* A fraction is a rational number p/q, where q != 0.*)
type fraction
(* Returns: make n d is n/d. Requires: d != 0. *)
val make : int -> int -> fraction
val numerator : fraction -> int
val denominator : fraction -> int
val toString : fraction -> string
val toReal : fraction -> float
val add : fraction -> fraction -> fraction
val mul : fraction -> fraction -> fraction
end
Here's one implementation of fractions -- what can go wrong here?
module Fraction1 : FRACTION =
struct
type fraction = { num:int; denom:int }
(* AF: The record {num=n; denom=d} represents fraction (n/d) *)
let make (n:int) (d:int) = {num=n, denom=d}
let numerator(x:fraction):int = x.num
let denominator(x:fraction):int = x.denom
let toString(x:fraction):string =
(string_of_int (numerator x)) ^ "/" ^
(string_of_int (denominator x))
let toReal(x:fraction):float =
(float_of_int (numerator x)) / (float_of_int (denominator x))
let mul (x:fraction) (y:fraction) : fraction =
make ((numerator x)*(numerator y))
((denominator x)*(denominator y))
let add (x:fraction) (y:fraction) : fraction =
make ((numerator x)*(denominator y) +
(numerator y)*(denominator x))
((denominator x)*(denominator y))
end
There are some weaknesses with this implementation. It would probably be better to check the denominator. Second, we're not reducing to smallest form. So we could overflow faster than we need to. And maybe we don't want to allow negative denominators.
We should pick a representation invariant that describes how we're going to represent legal fractions. Here is one choice:
module Fraction2 : FRACTION =
struct
type fraction = { num:int, denom:int }
(* AF: represents the fraction num/denom
* RI:
* (1) denom is always positive
* (2) always in most reduced form
*)
(* Returns the greatest common divisor of x and y.
* Requires: x, y are positive.
* Implementation: Euclid's algorithm.
*)
let rec gcd (x:int) (y:int) : int =
if x = 0 then y
else if (x < y) then gcd (y - x) x
else gcd y (x - y)
exception BadDenominator
let make (n:int) (d:int) : fraction =
if d = 0 then raise BadDenominator
else let g = gcd (abs n) (abs d) in
let n2 = n div g in
let d2 = d div g
in
if (d2 < 0) then {num = -n2, denom = -d2}
else {num = n2, denom = d2}
let numerator(x:fraction):int = x.num
let denominator(x:fraction):int = x.denom
let toString(x:fraction):string =
(string_of_int (numerator x)) ^ "/" ^
(string_of_int (denominator x))
let toReal(x:fraction):float =
(float_of_int (numerator x)) / (float_of_int (denominator x))
(* Notice that we didn't have to re-code mul or add --
* they automatically get reduced because we called
* make instead of building the data structure directly.
*)
let mul (x:fraction) (y:fraction) : fraction =
make ((numerator x)*(numerator y))
((denominator x)*(denominator y))
let add (x:fraction) (y:fraction) : fraction =
make ((numerator x)*(denominator y) +
(numerator y)*(denominator x))
((denominator x)*(denominator y))
end
A very useful abstraction is a dictionary: a mapping from strings to other values. A more general dictionary that maps from one arbitrary key type to another is usually called a map or an associative array, although sometimes “dictionary” is used for these as well. In any case, the implementation techniques are similar. Here's an interface for dictionaries:
module type DICTIONARY =
sig
(* An 'a dict is a mapping from strings to 'a.
We write {k1->v1, k2->v2, ...} for the dictionary which
maps k1 to v1, k2 to v2, and so forth. *)
type key = string
type 'a dict
(* make an empty dictionary carrying 'a values *)
val make : unit -> 'a dict
(* insert a key and value into the dictionary *)
val insert : 'a dict -> key -> 'a -> 'a dict
(* Return the value that a key maps to in the dictionary.
* Raise NotFound if there is not mapping for the key. *)
val lookup : 'a dict -> key -> 'a
exception NotFound
end
Here's an implementation discussed in recitation 6.
module FunctionDict : DICTIONARY =
struct
type key = string
type 'a dict = string -> 'a
(* The function f represents the mapping in which x is mapped to
* f(x), except for x such that f raises NotFound, which are not
* in the mapping.
*)
exception NotFound
let make () = fun _ -> raise NotFound
let lookup (d: 'a dict) (key: string) : 'a = d key
let insert (d:'a dict) (k:key) (x:'a) : 'a dict =
fun k' -> if k=k' then x else d k'
end
Here is another implementation: an association list
[(key1,x1),...,(keyn,xn)]
module AssocList : DICTIONARY =
struct
type key = string
type 'a dict = (key * 'a) list
(* AF: The list [(k1,v1), (k2,v2), ...] represents the dictionary
* {k1 -> v1, k2 -> v2, ...}, except that if a key occurs
* multiple times in the list, only the earliest one matters.
* RI: true.
*)
let make():'a dict = []
let insert (d:'a dict) (k:key) (x:'a) : 'a dict = (k,x)::d
exception NotFound
let lookup (d:'a dict) (k:key) : 'a =
match d with
[] -> raise NotFound
| ((k',x)::rest) ->
if (k = k') then x
else lookup rest k
end
This next implementation seems a little better for looking up values. Also note that the abstraction function does not need to specify what duplicate keys mean.
module SortedAssocList : DICTIONARY =
struct
type key = string
type 'a dict = (key * 'a) list
(* AF: The list [(k1,v1), (k2,v2), ...] represents the dictionary
* {k1 -> v1, k2 -> v2, ...}
* RI: The list is sorted by key and each key occurs only once
* in the list. *)
let make():'a dict = []
let insert (d:'a dict) (k:key) (x:'a) : 'a dict =
match d with
[] -> (k,x)::nil
| (k',x')::rest ->
(match String.compare(k,k') with
GREATER -> (k',x')::(insert rest k x)
| EQUAL -> (k,x)::rest
| LESS -> (k,x)::(k',x')::rest)
exception NotFound
let lookup (d:'a dict) (k:key) : 'a =
match d with
[] -> raise NotFound
| ((k',x)::rest) ->
(match String.compare(k,k') with
EQUAL -> x
| LESS -> raise NotFound
| GREATER -> lookup rest k)
end
Here is another implementation of dictionaries. This one uses a binary tree to keep the data -- the hope is that inserts or lookups will be proportional to log(n) where n is the number of items in the tree.
module AssocTree : DICTIONARY =
struct
type key = string
type 'a dict = Empty | Node of key * 'a * 'a dict * 'a dict
(* AF: Empty represents the empty mapping {}
* Node (key, datum, left, right) represents the union of the
* mappings {key -> datum}, AF(left), and AF(right).
* RI: for Nodes, data to the left have keys that
* are LESS than the datum and the keys of
* the data to the right. *)
let make():'a dict = Empty
let rec insert (d:'a dict) (k:key) (x:'a) : 'a dict =
match d with
Empty -> Node(k,x,Empty,Empty)
| Node (k', x', l, r) ->
(match String.compare k k' with
0 -> Node(k, x, l, r)
| -1 -> Node(k', x', insert l k x, r)
| 1 -> Node(k', x', l, insert r k x)
| _ -> raise (Failure "Impossible")
)
exception NotFound
let rec lookup (d:'a dict) (k:key) : 'a =
match d with
Empty -> raise NotFound
| Node(k',x,l,r) ->
(match String.compare k k' with
0 -> x
| -1 -> lookup l k
| 1 -> lookup r k
| _ -> raise (Failure "Impossible")
)
end