\( \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. References

Last Updated 2025-02-26 Wed 12:27.