CS 312 Recitation 8
Dictionaries, Queues, and Functors

Dictionaries (a.k.a. Maps or Associative Arrays)

A very useful type in programming is the dictionary. A dictionary is 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 the same. Here's a signature for dictionaries:

signature DICTIONARY =
    sig
	type key = string
       type 'a dict

	val make : unit -> 'a dict

	val insert : 'a dict -> key -> 'a -> 'a dict

	val lookup : 'a dict -> key -> 'a
	exception NotFound
    end

Here's a nice functional implementation of dictionaries that uses higher-order functions. The dictionary is represented just as a function from keys to values (string -> 'a) ! Initially the function has no binding; as new keys are inserted the function is extended with values for those keys:

structure FunctionDict :> DICTIONARY =
  struct
    type key = string
    type 'a dict = string -> 'a

    exception NotFound
  
    fun make () = fn _ => raise NotFound
 
    fun lookup (d: 'a dict) (key: string) : 'a = d key
  
    fun insert (d:'a dict) (k:key) (x:'a) : 'a dict = 
      fn k' => if k=k' then x else d k'
   end

Here is another implementation: an association list [(key1,x1),...,(keyn,xn)]

structure AssocList :> DICTIONARY =
    struct
	type key = string
        type 'a dict = (key * 'a) list

	fun make():'a dict = []

	fun insert (d:'a dict) (k:key) (x:'a) : 'a dict = (k,x)::d

	exception NotFound

	fun lookup (d:'a dict) (k:key) : 'a =
	    case d of
		[] => raise NotFound
	      | ((k',x)::rest) =>
		    if (k = k') then x
		    else lookup rest k
                    end

Functional Queues

Recall that  functional implementation of queue given in class using two stacks, s1 and s2. Stack s1 is used for enqueuing, s2 for dequeuing. When dequeuing, if stack s2 was empty, reverse s1 and treat it as the new s2. A linked list is a possible (but not the only) implementation for a stack.

Here is an interface for stacks:

  signature STACK = sig
      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
    end

Here is the interface for queues:

signature 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
    end

Here is the functional queue implementation using stacks:

structure Queue :> QUEUE = 
      struct
      structure S = Stack

      type 'a queue = 'a S.stack * 'a S.stack
      exception EmptyQueue

      val empty : 'a queue = (S.empty, S.empty)

      fun isEmpty ((s1,s2):'a queue) = 
        S.isEmpty s1 andalso S.isEmpty s2 

      fun enqueue (x:'a, (s1,s2):'a queue) : 'a queue = 
        (S.push (x,s1), s2)

      fun rev (s: 'a S.stack): 'a S.stack = let
        fun 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)                                                                               loop (s, S.empty)
      end

      fun dequeue ((s1,s2): 'a queue) : 'a * 'a queue = 
        if S.isEmpty s2
          then dequeue(S.empty, S.pop (rev s1)) 
                    handle S.EmptyStack => raise EmptyQueue
        else (s1, S.pop s2)

     fun map (f: 'a -> 'b) ((s1,s2): 'a queue): 'b queue = 
                (S.map f s1, S.map f s2)
  end

Functors

Suppose now that you had another implementation of stacks, say Stack2. Suppose you wanted to have at your disposal two implementations of Queue, one using Stack and the other using  Stack2.  The only way to achieve this with the above code is to duplicate it, creating two different versions of Queue. This is clearly not ideal - for one, you now have to maintain twice the code. Furthermore, it is not clear exactly what Queue assumes about the functionality of Stack. How do we know that substituting Stack2 for Stack will not break any of the Queue functionality? After all, it's possible that Stack and Stack2 don't even have the same signature.

To solve this problem, ML provides a mechanism called functors. The intuition behind functors is quite simple. In the above example, we know that our implementation of Queue will use a stack implementation. Creating a specific Queue structure could involve the following steps:

1. Create a stack structure S in the desired implementation (Stack  or Stack2),
2. Create a Queue structure making use of S, by passing S in as a parameter to some sort of "function".

For step 2, we need a "function" that takes in a structure and returns another structure - in this case, takes in a stack and returns a queue. Such "functions" are precisely the ML functors.

Our Queue functor will also need to specify (and check that its argument satisfies) all the stack functionality expected by Queue. Fortunately, we already know how to do this; after all, specifying functionality is exactly what signatures do. The Queue functor will specify a signature for the stack structure it expects, and will only accept structures that instantiate that signature.

Suppose this is the functionality desired by our Queue. Using the signature STACK defined above, we can write a Queue functor as follows:

functor QueueFn (S:STACK) : QUEUE = 
    struct
      ... 
      (* same code as before *)
  end

 structure s1 = Stack                                                                                                                                                                                                                                                                                                                                                                                              structure s2 = Stack2

It's now easy to create two corresponding queue structures by applying the functor:

structure q1 = QueueFn(s1)
structure q2 = QueueFn(s2)

Hence, passing different stack structures (s1 and s2) produces different queues (q1 and q2, respectively). As you see, functors provide a very powerful abstraction mechanism.

Another example of their use is when we need to construct a structure that will have an ordering, such as a Dictionary. For instance, the above dictionaries were defined specifically for string keys. We'd like to make them more general, to work with any types of keys. However, for arbitrary types we need to provide a function to compare keys. We can do this with functors. Define an ORDER signature:

signature ORDER = sig
   type key_type
   val compare: key_type * key_type -> order
end

functor DictionaryFn(O:ORDER) =
   struct
      (code uses key_type and function compare)
   end