Beyond signatures: Functors

Recall that the implementation of queue given in class made use
of two lists. More generally, a functional queue can be implemented 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 consider it the new s2. A linked list is a possible (but not the only)
implementation for a stack. Here is an 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

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.

More concretely, suppose we have the following stack signature:

signature STACK =Suppose this is the functionality desired by our Queue. We can write a Queue functor as follows:

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

functor QueueFn (S:STACK) =Suppose now that Stack and Stack2 both have the signature STACK. We create two stack structures, one using each implementation:

struct

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

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)

To complete the picture, note that we can also specify that we want the
result of the functor to conform to the QUEUE signature. Recall that
this signature was:

signature QUEUE =We can update our functor as follows:

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

functor QueueFn (S:STACK) : QUEUE =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 Binary Search Tree or a Dictionary. You can, of course, fix the ordering by explicitly passing in the ordering function to the ADT each time the ADT is constructed. However, we could also use functors to do this. Given the following signature:

struct

(rest of code as before)

end

signature ORDER = sigWe can create functors for Binary Search Trees and Dictionaries as follows:

type element

val compare: element * element -> order

end

functor BinarySearchTreeFn(O:ORDER) struct (BST code as before) end functor DictionaryFn(O:ORDER) = struct (Dictionary code as before) endWhich simplifies life for us quite a bit.

As an example, suppose we want to pass in two independent structures A and B to a functor FooFn. We proceed as follows:

functor FooFn (Arg : sigand we instantiate the functor as follows:

structure A : A_SIG

structure B : B_SIG end) =

(* body using Arg.A and Arg.B *)

structure Foo = FooFn (structSince this looks a bit clunky, ML provides a special abbreviation: we can forget about the surrounding structure and pass in the specification of the elements of the structure directly. Thus, the above example can be rewritten:

structure A = A

structure B = B

end)

functor FooFn (structure A : A_SIGYou may be slightly worried that this abbreviation loses the name for the wrapping structure (Arg). To reassure you, have a look at how the above abbreviation is actually implemented.

structure B : B_SIG) = ...

structure Foo = FooFn (structure A = A

structure B = B)

functor FooFn (structure A : A_SIGis implemented as

structure B : B_SIG) = ...

functor FooFn (uid : struct structure A : A_SIG structure B : B_SIG end) =As you see, because of the "open", we don't need to worry about the name of the wrapping structure.

struct

local

open uid

in

<body>

end

end

Footnote: the "local" keyword in ML is similar to "let", except it works at the declaration level rather than the expression level. Here's an example to see how it works:

- local

val a = 3

val b = 10

in

val x = a + b

val y = a * b

end;

val x = 13 : int

val y = 30 : int

- x;

val it = 13 : int

- a;

stdIn:139.1 Error: unbound variable or constructor: a

Notes adapted from Chapter 3 of Riccardo Pucella's SML Notes