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

Monad Transformer - SML

Table of Contents

1. Introduction

The basic idea is we want to combine monads together. Towards that end, we have a SML Functor which will "eat in" a monad, and produce a monad.

We have to implement an individual monad transformer as an individual functor. For example, 

functor StateT(type state
               structure M : MONAD) : MONAD =
struct
  type state = state;
  (* Type constructor *)
  type 'a t = (state -> 'a * state) M.t;

  fun return x = fn s => M.return (x,s);

  fun bind m f = fn s => M.bind (m s) (fn (x, s') => f x s');

  fun lift m = fn s => M.bind m (fn x => M.return (x,s));

  (* etc. *)
end;

2. Monad Transformers

I'm going to stick with the signature for a "generic" monad: 

signature MONAD = sig
  type 'a m;
  val return : 'a -> 'a m;
  val bind : 'a m -> ('a -> 'b m) -> 'b m;
  val exec : 'a m -> 'a;
end;

2.1. Reader Monad and Transformer

We typically want to have a way to read a fixed configuration environment, which is handled by the reader macro. We want the env type to be transparently ascribed, which requires some tricky signature constraint.

Using where type t1 = t2 in the opaquely ascribed signature allows us to make t1 "publicly transparent".

Also note that this is "lazy-ish" since the exec occurs within the body of the bind function. 

signature READER_MONAD = sig
  type env;
  val init_env : env;
  include MONAD;
  val map : ('a -> 'b) -> 'a m -> 'b m;
  val ask : env m;
end;

functor Reader(type Env
               val init_Env : Env) :> READER_MONAD
                                        where type env = Env =
struct
  type env = Env;
  val init_env = init_Env;
  datatype 'a m = Reader of (env -> 'a);

  fun exec (Reader r) = r init_env;

  fun return a = Reader (fn _ => a);

  fun bind (Reader r) k = Reader (fn e =>
                                   let
                                     val (Reader r') = k (r e);
                                   in
                                     (r' e)
                                   end);
  
  fun map f (Reader r) = Reader (f o r);

  val ask = Reader (fn x => x);
end;

And as a transformer… 

signature READER_T = sig
  type env;
  include MONAD;
  val ask : env m;
end;

functor ReaderT(structure M : MONAD
                type Env
                val init_Env : Env) :> READER_T
                                       where type env = Env =
struct
  type env = Env;
  datatype 'a m = ReaderT of (env -> 'a M.m);

  fun exec (ReaderT r) = M.exec (r init_Env);

  fun return a = ReaderT (fn _ => M.return a);

  fun bind (ReaderT m) k =
    ReaderT (fn e =>
                let
                  val a = M.exec (m e);
                  val (ReaderT b) = k a;
                in
                  b e
                end);

  val ask = ReaderT M.return;
end;

2.2. Writer Monad and Transformer

A lazy writer would have its type be unit -> 'a * string, and an eager writer would just be 'a * string.

More generally, we could replace string with any monoid. 

signature WRITER_MONAD = sig
  include MONAD;
  val get_log : 'a m -> string;
  val tell : string -> unit m;
end;

structure Writer :> WRITER_MONAD = struct
  type 'a m = 'a * string;

  fun return x = (x, "");

  fun bind (x, s1) f =
    let
      val (y, s2) = f x;
    in
      (y, s1 ^ s2)
    end;

  fun exec (x,_) = x;

  fun get_log (_, s) = s;
  
  fun tell s = ((), s);
end;

As a monad transformer, we would have something like: 

signature WRITER_T = sig
  structure M : MONAD;
  include MONAD;
  val get_log : 'a m -> string;
  val tell : string -> unit m;
end;

functor WriterT(M : MONAD) :> WRITER_T = struct
  structure M = M;
  datatype 'a m = WriterT of ('a * string) M.m;

  fun exec (WriterT m) =
    case M.exec m of
        (ans,_) => ans;

  fun get_log (WriterT m) =
    case M.exec m of
        (_,log) => log;

  fun return (a : 'a) = WriterT (M.return (a, ""));
  
  fun bind m f =
    let
      val a = (exec m);
      val s1 = get_log m;
      val m' = f a;
      val b = exec m';
      val s2 = get_log m';
    in
      WriterT (M.return (b, s1 ^ s2))
    end;

  fun tell w = WriterT (M.return ((), w));
end;

Again, we should generalize this from using strings to an arbitrary monoid.

2.3. Exception Monad and Transformer

In Standard ML, we can use the exn type for exceptions rather than allowing the user to provide one…well, in full generality, we could simply use a type variable (and then instantiate it to exn for the exception monad). 

structure ExceptionMonad : MONAD = struct
  datatype 'a m = V of 'a
                | E of exn;

  fun return a = V a;

  fun bind m f = case m of
                     (E e) => (E e)
                   | (V a) => f a;
  fun exec (V a) = a;
end;

But if we wanted to parametrize the "success" branch as a monad, then we need to use a monad transformer instead (NOTE: this is not a MONAD instance unless we fix the type of exceptions, but then catch would be impossible to implement using Standard ML's type system): 

signature EXCEPTION_T = sig
  type ('a, 'e) outcome;
  structure M : MONAD;

  val return : 'a -> ('a, 'e) outcome M.m;
  val exec : ('a, 'e) outcome M.m -> 'a;
  val bind : ('a,'e) outcome M.m ->
             ('a -> ('b,'e) outcome M.m) ->
             ('b,'e) outcome M.m;
  val throw : 'e -> ('a,'e) outcome M.m;
  val catch : ('a,'e1) outcome M.m ->
              ('e1 -> ('a,'e2) outcome M.m) ->
              ('a,'e2) outcome M.m;
end;

(* datatype ('a,'b) Either = Ok of 'a | Err of 'b; *)

functor ExceptionT(M : MONAD) :> EXCEPTION_T = struct
  datatype ('a, 'e) outcome = V of 'a | E of 'e;
  structure M : MONAD = M;

  fun exec m = case M.exec m of
                   (V a) => a;
  
  fun return a = M.return (V a);

  fun bind m f = M.bind m (fn (E e) => M.return (E e)
                            | (V x) => f x);

  fun lift x = M.bind x (fn v => M.return (V v));

  fun exec m = M.exec (M.bind m (fn (V x) => M.return x));

  fun throw e = M.return (E e);

  fun catch m f = M.bind m (fn (E e) => f e
                             | (V v) => M.return (V v));
end;

This is all a horrible idea, since Standard ML has exception handling built into it. Ostensibly, we could cobble these two things together, but that's a belt-and-suspenders "solution".

3. References

  • Sheng Liang, Paul Hudak, Mark Jones,
    "Monad transformers and modular interpreters".
    In POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 1995, pp.333–343 https://doi.org/10.1145/199448.199528
  • Mark P Jones,
    "Functional Programming with Overloading and Higher-Order Polymorphism".
    Eprint, 1995, 40 pages.
  • Martin Grabmuller,
    "Monad Transformers Step by Step".
    Citeseer 2006 draft.
  • Haskell's transformers library

3.1. OCaml Implementations

  • Łukasz Stafiniak,
    "Functional Programming, lecture 8: Monads".
    Slides
  • Xavier Leroy,
    "Functional programming languages, Part IV: monadic transformations, monadic programming".
    slides
  • Daniel Perez, Implementation
  • Jim Pryor,
    Monad Transformers

Last Updated 2025-02-26 Wed 17:02.