\( \DeclareMathOperator{\tr}{tr} \newcommand\D{\mathrm{d}} \newcommand\E{\mathrm{e}} \newcommand\I{\mathrm{i}} \newcommand\bigOh{\mathcal{O}} \newcommand{\cat}[1]{\mathbf{#1}} \newcommand\curl{\vec{\nabla}\times} \newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ZZ}{\mathbb{Z}} % For +---- metric \newcommand{\BDpos}{} \newcommand{\BDneg}{-} \newcommand{\BDposs}{\phantom{-}} \newcommand{\BDnegg}{-} \newcommand{\BDplus}{+} \newcommand{\BDminus}{-} % For -+++ metric \newcommand{\BDpos}{-} \newcommand{\BDposs}{-} \newcommand{\BDneg}{} \newcommand{\BDnegg}{\phantom{-}} \newcommand{\BDplus}{-} \newcommand{\BDminus}{+} \)
UP | HOME

Functors in SML

Table of Contents

1. Basic Idea

A functor in ML means a "parametrized module". It's an unfortunate choice of words, because "functor" has come to mean something completely different in functional programming. I will discuss that "something completely different" implemented in Standard ML.

In Haskell, the functor class consists of the fmap function and the <$ infix operator. I do not believe the <$ infix operator is necessary. We can then implement this as a signature: 

signature FUNCTOR = sig
  type 'a t;
  val map : ('a -> 'b) -> 'a t -> 'b t;
end;

There are two constraints to a functor:

  1. map id = id it preserves the identity function, and
  2. map (f o g) = (map f) o (map g) it preserves composition.

Note: I will refer to a module adhering to this signature generically as a FUNCTOR or a FUNCTOR, whereas the Standard ML parametrized structure is "functor" (all lower case) and Category Theoretic notions will use functor (or "Functor" if it starts a sentence).

1.1. Usefulness as AST

The basic use for a FUNCTOR is to encode an abstract syntax tree. Then the map function just transforms the leafs somehow.

For example, the syntax tree for propositional logic: 

structure Formula = struct
  datatype 'a t = Verum
                | Falsum
                | Atom of 'a
                | Not of 'a t
                | And of ('a t) * ('a t)
                | Or of ('a t) * ('a t)
                | Implies of ('a t) * ('a t)
                | Iff of ('a t) * ('a t);
  fun map f Verum = Verum
    | map f Falsum = Falsum
    | map f (Atom a) = Atom (f a)
    | map f (Not a) = Not (map f a) 
    | map f (And (a1,a2)) = And (map f a1, map f a2)
    | map f (Or (a1,a2)) = Or (map f a1, map f a2)
    | map f (Implies (a1,a2)) = Implies (map f a1, map f a2)
    | map f (Iff (a1,a2)) = Iff (map f a1, map f a2); 
end;

Observe that we did not ascribe the FUNCTOR signature to this, because it would "hide" the constructors And, Or, Verum, and so on. But we can still use Formula wherever a FUNCTOR is needed.

1.2. Example 2: Operations for a Free Monad

Another use for functors is to provide the "menu" of possible operations for some effect, which will be handled by a free monad.

For example, IO with "just" reading or writing a string to the screen can be handled simple as: 

(* A functor describing the operations with side-effects in IO *)
structure IO_Op = struct
  datatype 'a t = Print of (string * 'a)
                | Read of (string -> 'a);
  fun map f (Print (s,k)) = Print (s, f k)
    | map f (Read k) = Read (fn s => f (k s));
end;

2. Applicative Functors

One step towards monads is to consider applicative functors. This seems to originate from the paper:

  • Conor McBride and Ross Paterson,
    "Applicative Programming with Effects".
    Journal of Functional Programming 18 no.1 (2008), pages 1-13. Eprint

This allows us to describe effects (side-effects like IO, etc.) without dragging up the baroque framework of monads.

It's a typeclass, so we describe it using a signature. (See Haskell's Control.Applicative typeclass definition.) An applicative functor is still a functor, so we include FUNCTOR and add more operations to the signature. 

signature APPLICATIVE = sig
  include FUNCTOR;
  (* Our "ap" is Haskell's <*> *)
  val ap : ('a -> 'b) t -> 'a t -> 'b t;
  val pure : 'a -> 'a t;
  (* ...and possibly other quality-of-life functions. *)
end;

This satisfies the following laws:

  • Identity: ap (pure id) u = u
  • Composition: ap (pure o) (ap u (ap v w)) = ap u (ap v w)
  • Morphism: ap (pure f) (pure x) = pure (f x)
  • Interchange: ap u (pure x) = ap (pure (fn f => f x)) u

…in addition to the laws required for a functor.

It's common in Haskell to use f <*> x = ap f x, and also introduce: 

(* in APPLICATIVE *)
val <$> : ('a -> 'b) * 'a t -> 'b t;

(* implemented as: *)
fun (f <$> u) = ap (pure f) u;

Similarly, Haskell has liftA2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> c t as well as sequencing operators (*>) : 'a t -> 'b t -> 'b t and (<*) : 'a t -> 'b t -> 'a t. The sequencing operators evaluates the expressions to its left and right, then returns the value on the left or right.

2.1. Monads and Applicatives

Modern Haskell uses the hierarchy that monads are applicatives, and applicatives are functors.

3. References

Last Updated: Wed, 26 Feb 2025 17:16:04 -0800