Functors

By Cooper Pierce and Brandon Wu, February 2021

We have so far discussed the usage of modules for explicitly structuring our code, in that we are afforded a degree of modularity in how the different components of some software can fit together. We have used language like "swapping out" modules or "substituting" modules for one another, but this is very imprecise. What exactly do we mean when we say to swap one module for another? Certainly, it would be messy to have to go through our code and change every mention of StructureA for StructureB, and we would like to avoid some kind of global change that requires an extenuous amount of effort on the client's part.

Going through and changing every mention of a particular structure in order to achieve "modularization" is akin to saying that using a particular higher-order function by replacing specifically what each function parameter is in each invocation is how we can achieve "parameterization" in the function argument. In reality, this does not offer any more versatility. In this chapter, we will discuss functors, which are akin to higher-order modules, which are allowed to take other modules in as arguments.

Functors: The Basics

Firstly, consider the signature of a stack.

signature STACK =
sig
    type 'a t

    val push : 'a t -> 'a -> 'a t
    val pop : 'a t -> 'a option * 'a t
    val size : 'a t -> int
    val empty : 'a t
end

Suppose that we would like to extend the definition of a stack such that it has a limit on how many elements that it contains. However, we don't necessarily know which implementation of a stack to use - there could be several such existing implementations, so we would like to instead make our BoundedStack structure a parameter of an existing structure ascribing to STACK.

We will then use a very similar signature to STACK called BOUNDED_STACK, which is the exact same except for having an exception Full for use if a stack is given too many elements.

signature BOUNDED_STACK =
sig
    type 'a t
    exception Full

    val push : 'a t -> 'a -> 'a t
    val pop : 'a t -> 'a option * 'a t
    val size : 'a t -> int
    val empty : 'a t
end

We first consider the case where we have a hard limit of 10 items in a given stack.

functor BoundedStack (S : STACK) :> BOUNDED_STACK =
struct
    type 'a t = 'a S.t

    val limit = 10
    exception Full

    fun push S x =
        if S.size S >= limit
          then raise Full
          else S.push S x

    fun pop S = S.pop S

    fun size S = S.size S

    val empty = S.empty
end

We see that most of this code is duplicated - we have based the majority of the design of this BoundedStack in terms of S, which is the given implementation of a stack. The correctness of a BoundedStack is thus totally dependent on whether or not the given S is correct, but we achieve modularity in that we can freely swap out a structure ascribing to STACK for another when instantiating a given BoundedStack.

To put it concretely, suppose that we have two structures:

structure Stack1 :> STACK =
struct
    (* some code here *)
end

structure Stack2 :> STACK =
struct
    (* some code here *)
end

Then we can create instances of the BoundedStack functor as follows:

structure BoundedStack1 = BoundedStack(Stack1)
structure BoundedStack2 = BoundedStack(Stack2)

NOTE: SML functors are generative, meaning that applying the same functor to the same structure twice yields two unique structures. As such, if we had structure BS1 = BoundedStack(Stack1) and structure BS2 = BoundedStack(Stack1), then the types BS1.t and BS2.t are recognized as being two distinct types, despite the fact that they are "constructed" in the same manner.

BoundedStack1 and BoundedStack2 implement BOUNDED_STACK, so they all can access the fields of the BOUNDED_STACK signature. Presumably, the only change they display from Stack1 and Stack2 are in raising the exception Full when the stack is given more than ten elements.

Functors: Syntactic Sugar

SML offers some "syntactic sugar" for functor arguments, allowing us to (seemingly) parameterize them by terms other than structures. It is a little unsavory to have to hard code the limit of the BoundedStack within the functor itself, rather than having it be parameterized by the limit itself, so we can actually also write the following:

functor BoundedStack (structure S : STACK
                      val limit : int) :> BOUNDED_STACK =
struct
    type 'a t = 'a S.t

    exception Full

    fun push S x =
        if S.size S >= limit
          then raise Full
          else S.push S x

    fun pop S = S.pop S

    fun size S = S.size S

    val empty = S.empty
end

The only difference is that instead of taking in a single S : STACK, we specify "structure S : STACK val limit : int" within the parentheses of the functor's input. Note that there are no commas or delimiters other than spaces.

In reality, this is something of a lie. While this seems to give the impression that BoundedStack is taking in two things, a structure named S ascribing to STACK and a value of type int named limit, in reality functors can only take in other structures. This is thus syntactic sugar for the following code:

functor BoundedStack (UnnamedStructure :
                      sig
                        structure S : STACK
                        val limit : int
                      end) :> BOUNDED_STACK =
struct
    open UnnamedStructure
    (* same code as before *)
end

The open keyword specifies to open the namespace within a given module, effectively promoting all contents of it to the top level. Thus, if we were to open Stack1, as per our previous example, we could write push instead of Stack1.push, pop instead of Stack1.pop, and so on and so forth. Thus, what this syntactic sugar does is specify to take in a single structure ascribing to a signature that contains a structure ascribing to STACK and an int-typed value, named S and limit respectively.

CAUTION: This is a very important point to cognize! This can be the source of many frustrated hours of debugging due to a simple syntax error.

The reason why we must open UnnamedStructure in order to be able to use the same code is because we cannot say S.push, for instance, as we did in the original implementation of BoundedStack. We would instead have to specify UnnamedStructure.S.push, which is not what our previous code says. However, if we open UnnamedStructure first, the S structure is promoted to the top level, and we can now access it without first having to go through UnnamedStructure.

The reason for naming the input structure UnnamedStructure should hopefully now be clear. Indeed, it is a phantom structure of a sort, since in the syntactic sugar case, we never give it a name, and indeed we never really acknowledge its existence at all. Yet it is important to realize what is really happening, that there really is a structure being taken in as input, and then immediately opened for its contents.

What issues can occur if we forget about the existence of this syntactic sugar? Consider the following code:

functor BoundedStack (structure S : STACK) :> BOUNDED_STACK =
struct
    type 'a t = 'a S.t

    val limit = 10
    exception Full

    fun push S x =
        if S.size S >= limit
          then raise Full
          else S.push S x

    fun pop S = S.pop S

    fun size S = S.size S

    val empty = S.empty

end

structure BoundedStack1 = BoundedStack(Stack1)
structure BoundedStack2 = BoundedStack(Stack2)

This code will not compile! Can you see why?

The issue is that we have added a prefix of structure to S : STACK within the inputs. Even though we have only specified one field, not including the limit as a parameter, this will be interpreted as the following:

functor BoundedStack (UnnamedStructure :
                      sig
                        structure S : STACK
                      end) :> BOUNDED_STACK =
struct
    type 'a t = 'a S.t

    val limit = 10
    exception Full

    fun push S x =
        if S.size S >= limit
          then raise Full
          else S.push S x

    fun pop S = S.pop S

    fun size S = S.size S

    val empty = S.empty

end

structure BoundedStack1 = BoundedStack(Stack1)
structure BoundedStack2 = BoundedStack(Stack2)

Thus, BoundedStack is no longer a functor taking in a structure ascribing to STACK, but a functor taking in a structure ascribing to sig structure S: STACK end. In other words, taking in a structure containing a structure ascrbing to STACK! Thus, the line structure BoundedStack1 = BoundedStack(Stack1) will not type-check, as Stack1 does not ascribe to the same signature that BoundedStack is expecting. This one simple syntax error can be the source of much pain and frustration, so we caution the reader to be particular with their syntax, and mindful of what is really happening under the hood.

Case study: Typeclasses

Certain types have some functionality or operation in common. Depending on the operation in question, we can say that these types fall into the same typeclass, which is a common interface consisting of a type and the desired operations. Note that typeclass membership is not a formally defined relationship, but instead a useful categorization that we use in order to classify types that we intend to parameterize some implementation over.

For a concrete example of a typeclass, consider the ORDERED typeclass.

signature ORDERED =
sig
    type t
    val compare : t * t -> order
end

The ORDERED typeclass consists of those types that admit a sensible ordering, which we will not (and perhaps cannot) define. Thus, we can witness int and string as valid instances of the ORDERED typeclass with the following structures:

structure IntOrder : ORDERED =
struct
    type t = int
    val compare = Int.compare
end

structure StringOrder : ORDERED =
struct
    type t = string
    val compare = String.compare
end

Note that it is useful, in this case, for our instances of the ORDERED typeclass to be transparently ascribed, since it is the whole point that we are aware of the type that the typeclass is associated with.

NOTE: In actuality, we use transparent ascription as somewhat of a sledgehammer to avoid having to talk about a different language construct, namely where clauses. A where clause modifies a signature containing an abstract type, and concretely specifies what that type should be. For instance, we could discuss the signature signature ORDERED type t end where type t = int. A structure ascribing to this signature would "publish" the details of the type t (which is really an int), the same way that transparent ascription would. With where clauses, however, if there are multiple abstract types, we can be selective about which ones that are made "transparent". For the purposes of this chapter, however, we will largely avoid where clauses.

These definitions come very naturally from the fact that the String and Int libraries included with the Standard ML basis library already implement compare fields, however we can also define types such as int list to be instances of ORDERED:

structure IntListOrder : ORDERED =
struct
    type t = int list
    fun compare [] [] = EQUAL
      | compare [] ys = LESS
      | compare xs [] = GREATER
      | compare (x::xs) (y::ys) =
        case Int.compare (x, y) of
            EQUAL => compare xs ys
          | LESS => LESS
          | GREATER => GREATER
end

This structure defines a lexicographic ordering on int lists, using the fact that values of type int are already ordered. It prioritizes the relative comparison of the corresponding elements of both lists first, and then the length (akin to how a dictionary is ordered).

Indeed, we can take this one step further and see that lexicographic orderings form a functor, in that we can parameterize the ordering of some type of list, given that we can order the elements of the list. Like a higher-order function, this saves us from having to repeat the same code over and over to declare StringListOrder and CharListOrder structures, instead encapsulating the common pattern. We can implement the LexicListOrder functor as follows:

functor LexicListOrder (O : ORDERED) : ORDERED =
struct
    type t = O.t list
    fun compare [] [] = EQUAL
      | compare [] ys = LESS
      | compare xs [] = GREATER
      | compare (x::xs) (y::ys) =
        case O.compare (x, y) of
            EQUAL => compare xs ys
          | LESS => LESS
          | GREATER => GREATER
end

Note that since an instantiation of the LexicListOrder functor is itself a structure ascribing to ORDERED, it can be "passed in" as input to itself, resulting in any type of nested list being an instance of ORDERED, so long as the base type is also an instance of ORDERED.

It is also useful to note that equality types in Standard ML are essentially a language-supported typeclass, akin to inbuilt support for the following signature:

signature EQ =
sig
    type t
    val equal : t * t -> bool
end

The operations for equal for each "instance" of the typeclass are instead defined by Standard ML itself, and not user-defined. Thus, we can think of the equality operator = as simply invoking the T.equal method for the proper typeclass T, defined by the type that is being compared for equality.

In this next section, we will explore a concrete use for typeclasses when designing functors.

Case study: Red-black trees

Typeclasses can be important when we are attempting to place some greater constraint on the types that may instantiate some universal type. In certain cases, we do not want the types that we are considering to truly be any type, but any of a limited subset of types that share some common characteristic or implement some operation. We will study the use of red-black trees as the underlying data structure for dictionaries.

A dictionary is a simple data structure that maps keys to values. Consider its signature given below.

signature DICT =
sig
    type key
    type 'a dict
    val empty : 'a dict
    val insert : 'a dict -> key * 'a -> 'a dict
    val lookup : 'a dict -> key -> 'a option
end

It is a well-known fact that, utilizing a kind of balanced binary tree data structure, dictionaries can be implemented with an $O(\log n)$ insert and lookup operation, as opposed to $O(n)$ for other data structures such as lists. While there are many different implementations of balanced binary trees, we will consider a particular variant known as red-black trees.

[Red-black tree]: A variant of self-balancing binary tree that ensures logarithmic search and insert time. It is named because of its nodes, which are marked as either red or black. Furthermore, it obeys the following properties:

1. All leaves are black.
2. The children of a red node must be black.
3. Any path from a given node to a leaf node must go through the same number of black nodes.

Note that as a variant of binary search tree, a red-black tree must also satisfy the invariant that the key stored at a node must be greater than or equal to every key in the left subtree, and less than or equal to every key in the right subtree.

It is easy to reason about why this schema ensures that we have the proper asymptotic bound for search - the third property in particular ensures that, for any path from the root, the length of the longest path from the root to a leaf is at most twice that of the shortest path. This is because the longest such path you can construct from the root to a leaf (minimizing black nodes) is by alternating black and red nodes.

This means that a given red-black tree is not as strictly balanced as some other variants (for instance, AVL trees), however it is always approximately balanced.

We would like to create a structure for red-black tree dictionaries. There are some options that we have - we could simply hard-code a TypeRedBlackDict :> DICT for any type Type, except that this would entail quite a bit of repeated code (and exertion on our part). Another solution would be to make the type of 'a dict doubly-polymorphic instead - something like an ('a, 'b) dict, where 'a is the type of the dict's keys and 'b the type of its contents. However, then we lose the guarantee that 'a is a type that supports comparison, which means that we cannot satisfy the tree's invariants.

The solution we will turn to is exactly similar to that as discussed in the previous section - we will instead design a RedBlackDict functor that takes in a typeclass implementing ORDERED, and exports a structure whose keys are the type of the given typeclass. We thus will define our functor with the following preliminaries:

functor RedBlackDict (Key : ORDERED) :> DICT where type key = Key.t =
struct
    type key = Key.t
    datatype color = Red | Black
    datatype 'a dict = Leaf | Node of 'a dict * (color * (key * 'a)) * 'a dict

    val empty = Leaf
    (* ... *)
end

Because we take as input a Key structure ascribing to ORDERED, we have access to the Key.compare function, which we will use when inserting into our dictionary. We define a color type (which only consists of the constant constructors Red and Black) for tagging the nodes of the red-black tree (leaves are considered to be black).

Note: We use the where syntax to indicate that the type key will be the same as Key.t to the outside world. This is important because our RedBlackDict is opaquely ascribed, meaning that without this syntax, we wouldn't know what the type of key is, and thus could not actually add any keys! While before we avoided using where by just making the ascription transparent, we don't want to do that here, because we don't want the outside world to mess with our red-black tree and potentially mess up the invariant!

The question becomes: how should we implement insert? We cannot be so naive as to simply insert as we would in an ordinary binary search tree, as this would quickly cause problems with our invariants. In particular, we must be mindful of the black height invariant, saying that all paths to leaves must have the same number of black nodes on them.

The easiest case to tackle for insert is the Leaf case. How should we finish the definition of fun insert Leaf (k, v) = ? Well, clearly we must insert a Node(Leaf, (c, (k, v)), Leaf) for some color c. Note that since a Leaf is considered to be colored black, if we choose c to be Black, we will run into issues with our black height invariant - we have replaced a Leaf (a subtree of black height 1) with a subtree of black height 2! This will disproportionately affect the black height of paths ending in this subtree, thus causing the invariant to be violated.

Thus, the only sensible choice we can commit is to insert as a Red node. The astute reader may see that this will quickly cause issues - we will address this shortly. Thus, we can write

fun insert Leaf (k, v) = Node(Leaf, (Red, (k, v)), Leaf)
  | insert (Node (L, (c', (k', v')), R)) (k, v) = ...

How should we handle the Node case? Well, insertion really only happens at the leaves - the only thing that we can do at a Node is to propagate the change throughout the tree until it gets to where it needs to be. We have seen that this schema of an "always-red" insertion maintains the black-height invariant, however there is the red-children invariant as well - the children of a red node must themselves be red. This invariant is the one that we are not respecting, with our current schema.

So we only run into an issue when we insert into the tree such that the new node is the child of a red node. Furthermore, we know that, if the tree that we are inserting into is truly a red-black tree, it must respect the red-children invariant, and thus the the parent of the inserted node must itself have a black parent. Thus, there can only be four cases for the "site" of the insertion:

Fig 1. Illustration of the four cases of the red-children invariant being broken following insertion. The inserted nodes are marked with a "plus".

Such an invariant violation is only a local concern, however. All that is needed in order to restore the invariant is to simple rotate the site of violation, and do a simple recoloring. We will illustrate only the first case, and the rest follow similarly. You may verify for yourself that this continues to preserve the ordering and black-height invariants.

Fig 2. Illustration of the "balancing" necessary in order to preserve the red-children invariant in Case 1 of Fig. 1.

We thus write the following function which takes care of all four cases.

fun balance (Node(Node(Node(a,(Red,x),b), (Red,y), c), (Black, z), d)) =
            Node(Node(a,(Black,x),b),  (Red,y), Node(c,(Black,z),d))
  | balance (Node(a,(Black,x), Node(Node(b,(Red,y),c), (Red, z), d))) =
            Node(Node(a,(Black,x),b), (Red,y), Node(c,(Black,z), d))
  | balance (Node(Node(a, (Red,x), Node(b,(Red,y),c)), (Black,z), d)) =
            Node(Node(a,(Black,x),b), (Red, y), Node(c,(Black,z),d))
  | balance (Node(a, (Black,x), Node(b, (Red,y), Node(c,(Red,z), d)))) =
            Node(Node(a,(Black,x),b), (Red,y), Node(c,(Black,z), d))
  | balance T = T

Note that if we are not in any of the four described cases, balance simply acts as the identity function, as there is no invariant being broken.

However, this rotation may itself cause another site of red-children invariant violation, slightly farther up. As such, we must propagate this balancing operation as far up as necessary, in order to produce a proper binary tree at the very end. To this end, we can write the following code for the inductive case of insert:

fun insert Leaf (k, v) = Node(Leaf, (Red, (k, v)), Leaf)
  | insert (Node (L, (c', (k', v')), R)) (k, v) =
    case Key.compare (k, k') of
        LESS => balance(Node(insert L (k, v), (c', (k', v')), R))
      | EQUAL => Node(L, (c', (k, v)), R)
      | GREATER => balance(Node(L, (c', (k', v')), insert R (k ,v)))

This code ensures that, after descending into a subtree in order to insert the given key and value, a balancing operation is immediately performed once the insertion is complete. This ensures that we have a bottom-up propagation of balancings, immediately after completing the insertions. Note that because balance acts as the identity function on anything that does not pattern-match to either of the four cases, we perform only a negligible amount of extra checks at each recursive call, and ultimately are only concerned with those four cases.

However, this code is not complete. There is a minor edge case that remains - what if we are too close to the root for any of the four cases to apply? Our previous analysis relied on the fact that we could assume that the parent of our inserted node was red, and thus had a black parent - what of the case where the parent of the inserted node has no parent?

Consider the case illustrated below:

Fig 3. Demonstration of potential issues in inserting nodes at the root when lacking a black parent.

As we can see here, our previous reasoning does not catch this red-children violation because it does not conform to our previous cases, by virtue of the inserted node not having a grandfather. This case can only happen at the root, however, since that is the only location where that can occur. As a result, the simple solution is to simply make the root of any red-black tree black - it will preserve the black height invariant, but also result in this red-red violation being impossible. We can amend our code as follows:

fun insert' Leaf (k, v) = Node(Leaf, (Red, (k, v)), Leaf)
  | insert' (Node (L, (c', (k', v')), R)) (k, v) =
    case Key.compare (k, k') of
        LESS => balance(Node(insert' L (k, v), (c', (k', v')), R))
      | EQUAL => Node(L, (c', (k, v)), R)
      | GREATER => balance(Node(L, (c', (k', v')), insert' R (k ,v)))

fun insert T (k, v) =
    case insert' T (k, v) of
        Leaf => Leaf
      | Node (L, (_, (k', v')), R) => Node(L, (Black, (k', v')), R)

Finally, this results in our completed code for the insert function. Note that because of the signature that we are ascribing to, helper functions such as balance and insert will not be visible to the client of the module, so there is no harm in declaring them within the namespace of the functor.

Our completed code for a red-black tree implementation of dictionaries is thus as follows. Note that the implementation of lookup is very straightforward, and

functor RedBlackDict (Key : ORDERED) :> DICT where type key = Key.t =
struct
    type key = Key.t
    datatype color = Red | Black
    datatype 'a dict = Leaf | Node of 'a dict * (color * (key * 'a)) * 'a dict

    val empty = Leaf

    fun balance (Node(Node(Node(a,(Red,x),b), (Red,y), c), (Black, z), d)) =
                Node(Node(a,(Black,x),b),  (Red,y), Node(c,(Black,z),d))
      | balance (Node(a,(Black,x), Node(Node(b,(Red,y),c), (Red, z), d))) =
                Node(Node(a,(Black,x),b), (Red,y), Node(c,(Black,z), d))
      | balance (Node(Node(a, (Red,x), Node(b,(Red,y),c)), (Black,z), d)) =
                Node(Node(a,(Black,x),b), (Red, y), Node(c,(Black,z),d))
      | balance (Node(a, (Black,x), Node(b, (Red,y), Node(c,(Red,z), d)))) =
                Node(Node(a,(Black,x),b), (Red,y), Node(c,(Black,z), d))
      | balance T = T

    fun insert' Leaf (k, v) = Node(Leaf, (Red, (k, v)), Leaf)
      | insert' (Node (L, (c', (k', v')), R)) (k, v) =
        case Key.compare (k, k') of
            LESS => balance(Node(insert' L (k, v), (c', (k', v')), R))
          | EQUAL => Node(L, (c', (k, v)), R)
          | GREATER => balance(Node(L, (c', (k', v')), insert' R (k ,v)))

    fun insert T (k, v) =
        case insert' T (k, v) of
            Leaf => Leaf
          | Node (L, (_, (k', v')), R) => Node(L, (Black, (k', v')), R)

    fun lookup Leaf k = NONE
      | lookup (Node (L, (_, (k', v)), R)) k =
        case Key.compare (k, k') of
            LESS => lookup L k
          | EQUAL => SOME v
          | GREATER => lookup R k
end

In the end, usage of modules allows us to write a powerful, parameterized implementation of a dictionary interface, in such a way that we ensure that our representation invariants are respected throughout each operation. By making a structure ascribing to the ORDERED typeclass a parameter of the functor RedBlackDict, we allow powerful generality in the type of the key to the dictionary, without having to introduce additional overhead in the functions of the module itself.

Conclusions

In this chapter, we have seen how functors are a potent tool when structuring our code, that allows us to enforce modularity and implement code reuse within the language itself. Functors also form the basis for a kind of higher-order module, where we can parameterize the structures we are capable of creating by other structures themselves, resulting in a greater degree of expression and versatility not unlike those of higher-order functions themselves.