# Recitation 7: Functional stacks and queues, dictionaries, fractions

## Functional data structures

In this recitation, we look at examples of structures and signatures that implement data structures. We show that stacks and queues can be implemented efficiently in a functional style.

What is a functional stack, or a functional queue? It is a data structure for which the operations do not change the data structure, but rather create a new data structure, with the appropriate modifications, instead of changing it in-place. In imperative languages, data operations generally support destructive update — “destructive” in the sense that after the update is done, the original data structure is gone. Functional abstractions support nondestructive updates: the original value is still around, unmodified, so code that was using it is unaffected. For efficiency, it is important to implement nondestructive updates not by creating an entirely new data structure, but by sharing as much as possible with the original data structure.

## Stacks

Recall a stack: a last-in first-out (LIFO) queue. Just like lists, the stack operations fundamentally do not care about the type of the values stored, so it is a naturally polymorphic data structure.

Here is a possible signature for functional stacks:

```module type STACK =
sig
(* A stack of elements of type 'a. We write  to
* denote a stack whose top element is a1, with successive
* elements a2, a3,...an. *)
type 'a stack

exception EmptyStack

(* The empty stack. *)
val empty : 'a stack

(* Whether this stack is empty. *)
val isEmpty : 'a stack -> bool

(* Returns a new stack with x pushed onto the top. *)
val push : ('a * 'a stack) -> 'a stack

(* Returns a new stack with the top element popped off. *)
val pop : 'a stack -> 'a stack

(* The top element of the stack. *)
val top : 'a stack -> 'a

(* map(f) maps one stack into a corresponding stack, using f. *)
val map : ('a -> 'b) -> 'a stack -> 'b stack

(* app(f) applies f to every element of the stack, top to bottom. *)
val app : ('a -> unit) -> 'a stack -> unit
end
```

This signature specifies a parameterized abstract type for stack. Notice the type variable `'a`. The signature also specifies the empty stack value, and functions to check if a stack is empty, and to perform push, pop and top operations on the stack. Moreover, we specify functions map and app to walk over the values of the stack.

We also declare an exception `EmptyStack` to be raised by top and pop operations when the stack is empty.

Here is the simplest implementation of stacks that matches the above signature. It is implemented in terms of lists.

```module Stack : STACK =
struct
type 'a stack = 'a list
exception EmptyStack

let empty : 'a stack = []

let isEmpty (l : 'a list) : bool = l = []

let push ((x : 'a), (l : 'a stack)) : 'a stack = x :: l

let pop (l : 'a stack) : 'a stack =
match l with
[] -> raise EmptyStack
| x :: xs -> xs

let top (l : 'a stack) : 'a =
match l with
[] -> raise EmptyStack
| x :: xs -> x

let map (f : 'a -> 'b) (l : 'a stack) : 'b stack = List.map f l
let app (f : 'a -> unit) (l : 'a stack) : unit = List.iter f l
end
```

Up until now, we have been defining exceptions solely in order to raise them and interrupt the executing program. Just like in Java, it is also possible to catch exceptions, which is termed 'handling an exception' in OCaml.

As an example, consider the following example. In the above code, we have implemented top and pop respectively as functions that return the first element of the list and the rest of the list. OCaml already defines functions to do just that, namely `List.hd` and `List.tl` (for head and tail). The function `hd` takes a list as argument and returns the first element of the list, or raises the exception `Failure` if the list is empty. Similarly for `tl`. One would like to simply be able to write in `Stack`:

```let top (l : 'a stack) : 'a = List.hd l
let pop (l : 'a stack) : 'a stack = List.tl l
```

However, if passed an empty stack, `top` and `pop` should raise the `EmptyStack` exception. As written above, the exception `Failure` would be raised. What we need to do is intercept (or handle) the exception, and raise the right one. Here's one way to do it:

```let top (l : 'a stack) : 'a =
try List.hd l with Failure _ -> raise EmptyStack
let pop (l : 'a stack) : 'a stack =
try List.tl l with Failure _ -> raise EmptyStack
```

The syntax for handling exceptions is as follows:

```try e with exn -> e'
```

where `e` is the expression to evaluate, and if `e` raises an exception that matches `exn`, then expression `e'` is evaluated instead. The type of `e` and `e'` must be the same.

## Queues

Let us write an example more interesting than stacks. After all, from the above, one can see that they are just lists. Consider the queue data structure, a first-in first-out data structure. Again, we consider functional queues. Here is a possible signature:

```module type QUEUE =
sig
type 'a queue
exception EmptyQueue

val empty : 'a queue
val isEmpty : 'a queue -> bool

val enqueue : ('a * 'a queue) -> 'a queue
val dequeue : 'a queue -> 'a queue
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)
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 rec loop ((prev : 'a S.stack), (curr : 'a S.stack))
: 'a S.stack =
if S.isEmpty prev
then curr
else loop (S.pop prev, S.push (S.top prev, curr))
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
```

We learned about folding last week. In the above implementation, the stack reversal could have been done using fold. However, since the Stack module does not specify a fold operation, and the implementation of the Stack as a list is hidden from the Queue module, we need something more. The Stack signature should specify a fold operation that will help its users to iterate over its elements.

## Dictionaries

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

(* applies a function to all the elements of a dictionary;
i.e., if a dictionary d maps a string s to an element a,
then the dictionary (map f d) will map s to f(a). *)
val map : ('a -> 'b) -> 'a dict -> 'b dict

end
```

Here is an implementation using association lists `[(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 rec lookup (d : 'a dict) (k : key) : 'a =
match d with
[] -> raise NotFound
| (k', x) :: rest ->
if k = k' then x
else lookup rest k

let map (f : 'a -> 'b) (d : 'a dict) =
List.map (fun (k, a) -> (k, f a)) d
end
```

Here's another implementation using higher-order functions as dictionaries.

```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 that are not in the mapping, in which case
* f raises NotFound.
*)
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'
let map (f : 'a -> 'b) (d : 'a dict) = fun k -> f (d 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 rec insert (d : 'a dict) (k : key) (x : 'a) : 'a dict =
match d with
[] -> (k, x) :: []
| (k', x') :: rest ->
match String.compare k k' with
1 -> (k', x') :: (insert rest k x)
| 0 -> (k, x) :: rest
| -1 -> (k, x) :: (k', x') :: rest
| _ -> failwith "Impossible"

exception NotFound

let rec lookup (d : 'a dict) (k : key) : 'a =
match d with
[] -> raise NotFound
| (k', x) :: rest ->
match String.compare k k' with
0 -> x
| -1 -> raise NotFound
| 1 -> lookup rest k
| _ -> failwith "Impossible"

let map (f : 'a -> 'b) (d : 'a dict) =
List.map (fun (k,a) -> (k, f a)) d
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)
| _ -> failwith "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
| _ -> failwith "Impossible"

let rec map (f : 'a -> 'b) (d : 'a dict) =
match d with
Empty -> Empty
| Node (k, x, l, r) -> Node (k, f x, map f l, map f r)
end
```

## Fractions

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 (numerator x)) /. (float (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)

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 / g in
let d2 = d / 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 (numerator x)) /. (float (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
```