Editing Standard ML (section)

====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.