Editing Standard ML (section)

===Module system===
Standard ML's advanced module system allows programs to be decomposed into hierarchically organized ''structures'' of logically related type and value definitions. Modules provide not only [[namespace]] control but also abstraction, in the sense that they allow the definition of [[abstract data type]]s. Three main syntactic constructs comprise the module system: signatures, structures and functors.

====Signatures====
A ''signature'' is an [[Interface (computing)|interface]], usually thought of as a type for a structure; it specifies the names of all entities provided by the structure, the [[arity]] of each type component, the type of each value component, and the signature of each substructure. The definitions of type components are optional; type components whose definitions are hidden are ''abstract types''.

For example, the signature for a [[Queue (data structure)|queue]] may be:

<syntaxhighlight lang="sml">
signature QUEUE = sig
    type 'a queue
    exception QueueError;
    val empty     : 'a queue
    val isEmpty   : 'a queue -> bool
    val singleton : 'a -> 'a queue
    val fromList  : 'a list -> 'a queue
    val insert    : 'a * 'a queue -> 'a queue
    val peek      : 'a queue -> 'a
    val remove    : 'a queue -> 'a * 'a queue
end
</syntaxhighlight>

This signature describes a module that provides a polymorphic type {{code|lang=sml|'a queue}}, {{code|lang=sml|exception QueueError}}, and values that define basic operations on queues.

====Structures====
A ''structure'' is a module; it consists of a collection of types, exceptions, values and structures (called ''substructures'') packaged together into a logical unit.

A queue structure can be implemented as follows:

<syntaxhighlight lang="sml">
structure TwoListQueue :> QUEUE = struct
    type 'a queue = 'a list * 'a list

    exception QueueError;

    val empty = ([], [])

    fun isEmpty ([], []) = true
      | isEmpty _ = false

    fun singleton a = ([], [a])

    fun fromList a = ([], a)

    fun insert (a, ([], [])) = singleton a
      | insert (a, (ins, outs)) = (a :: ins, outs)

    fun peek (_, []) = raise QueueError
      | peek (ins, outs) = List.hd outs

    fun remove (_, []) = raise QueueError
      | remove (ins, [a]) = (a, ([], List.rev ins))
      | remove (ins, a :: outs) = (a, (ins, outs))
end
</syntaxhighlight>

This definition declares that {{code|lang=sml|structure TwoListQueue}} implements {{code|lang=sml|signature QUEUE}}. Furthermore, the ''opaque ascription'' denoted by {{code|lang=sml|:>}} states that any types which are not defined in the signature (i.e. {{code|lang=sml|type 'a queue}}) should be abstract, meaning that the definition of a queue as a pair of lists is not visible outside the module. The structure implements all of the definitions in the signature.

The types and values in a structure can be accessed with "dot notation":

<syntaxhighlight lang="sml">
val q : string TwoListQueue.queue = TwoListQueue.empty
val q' = TwoListQueue.insert (Real.toString Math.pi, q)
</syntaxhighlight>

====Functors====
A ''functor'' is a function from structures to structures; that is, a functor accepts one or more arguments, which are usually structures of a given signature, and produces a structure as its result. Functors are used to implement [[Generic programming|generic]] data structures and algorithms.

One popular algorithm<ref name="bfs"/> for [[breadth-first search]] of trees makes use of queues. Here is a version of that algorithm parameterized over an abstract queue structure:

<syntaxhighlight lang="sml">
(* after Okasaki, ICFP, 2000 *)
functor BFS (Q: QUEUE) = struct
  datatype 'a tree = E | T of 'a * 'a tree * 'a tree

  local
    fun bfsQ q = if Q.isEmpty q then [] else search (Q.remove q)
    and search (E, q) = bfsQ q
      | search (T (x, l, r), q) = x :: bfsQ (insert (insert q l) r)
    and insert q a = Q.insert (a, q)
  in
    fun bfs t = bfsQ (Q.singleton t)
  end
end

structure QueueBFS = BFS (TwoListQueue)
</syntaxhighlight>

Within {{code|lang=sml|functor BFS}}, the representation of the queue is not visible. More concretely, there is no way to select the first list in the two-list queue, if that is indeed the representation being used. This [[data abstraction]] mechanism makes the breadth-first search truly agnostic to the queue's implementation. This is in general desirable; in this case, the queue structure can safely maintain any logical invariants on which its correctness depends behind the bulletproof wall of abstraction.