ML abstract data type

Question

I am trying to use abstract data types in Standard ML. For example, I could write a signature Queue, and two queues implementations by defining two structures as queues:

signature Queue = ...
structure AQueue :> Queue = ...
structure BQueue :> Queue = ...

Now I'd like to write generic functions/values for queues, that it doesn't matter which queue I am using (AQueue or BQueue). For example, I'd like to write the following:

val double1 = Queue.enqueue (1, Queue.enqueue (1, Queue.empty))

I think I should mention the Queue.queue type (assumming it is named like that in signature Queue) somewhere... should I open Queue? Can this be done? This seems like it should be a fairy common situation with ADTs, but I do not know where to read... all I found is how to define signatures/structures, but not how to use them.

Answer 1

That's where functors come in: you write a module parameterised by which queue it uses:

functor Client(Queue : QUEUE) =
struct
  val double1 = Queue.enqueue (1, Queue.enqueue (1, Queue.empty))
  ...
end

You can then instantiate this module with specific choices of queue implementations:

structure AClient = Client(AQueue)
structure BClient = Client(BQueue)

Btw, signature names are typically written all-caps, to distinguish them from structures.