\( \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}} \)
UP | HOME

State Monad - SML

Table of Contents

1. Introduction

We can think of the State monad as a Reader monad which is also a Writer monad, but that's probably not the best way to derive the State monad.

Wadler introduced the idea of encoding state into a monad back in 1992 (if not earlier) in his paper "The Essence of Functional Programming". But the formalism of State in terms of StateT monad transformers seems to be from Jones's 1995 paper "Functional Programming with Overloading and Higher-Order Polymorphism".

Confusingly, early papers mix up the State monad with the ST monad. We can view this as a generalization of the IO Monad, where we now have: 

type RealWorld = ...

type IO a = State RealWorld a

2. Heuristic Derivation

We basically have a state be described along the lines of: 

datatype ('s,'a) State = State of ('s -> 'a*'s);

This is tempting, but wrong. Why?

We do not want to export the constructor, because we do not want the user to do pattern matching. We could ostensibly just do: 

type ('s, 'a) State = 's -> 'a * 's;

But this won't do. Why not? Because almost any function could qualify for being a term of type State. That's bad.

What we do is: 

abstype ('s, 'a) State = State of ('s -> 'a * 's)
where
  fun state (f : 's -> 'a * 's) = State f;
  fun runState t st = (* magic... *);
  fun return x = state (fn st => (x, st));

  (* "k" for "kontinuation" *)
  fun bind act k = state (fn st =>
                             let val (x, st') = runState act st
                             in runState (k x) st'
                             end);
end;

Probably a more honest answer is to have State of {runState : 's -> 'a*'s}.

2.1. Stack Computation

One fascinating derivation is to consider a simple "stack computer", modeled by a list of integers. We also have a register (a "top of stack" value). The "state" 's in this case is int list, the 'a in this case is the "top of stack" register int.

Here return (x : int) = State (fn s => (x, s)) updates the "top of stack" register.

The bind function composes state-transition functions: 

(* f : top-of-stack -> State *)
fun bind (State st) f = State (fn s => let val (x, s') = st s
                                           val (State st') = f x
                                       in st' s'
                                       end);

We would then have the basic operations like push, pop, top, etc., be implemented using monadic constructor: 

datatype ('a * 's) State = State of ('s -> 'a * 's);

(* push : int -> State (int list) int *)
fun push n = State (fn s => (n, n::s));

(* pop : State (int list) int *)
val pop = State (fn (x::xs) => (x, xs));

(* top : State (int list) int *)
val top = State (fn (x::xs) => (x, x::xs));

I really like this example, since it emphasizes with clarity the essential aspect of the state monad as abstracting the notion of a stateful computation. I found this example from:

3. Implementation Details

3.1. Higher-Order Types

Haskell can have higher-order types (where types and type constructors are given as constructors). If we try to naively translate this into Standard ML, there is nothing "obviously" comparable.

What we should do instead is to use SML Functors. After all, we have a Monad be encoded using an ML structure, so if our intuitive understanding of a Monad transformer is (according to Haskell): 

class (forall m. Monad m => Monad (t m)) => MonadTrans t where
    lift :: (Monad m) => m a -> t m a

It has to satisfy the following two laws:

  1. lift . return = return
  2. lift (m >>= f) = lift m >>= (lift . f)

What we should do is define a monad transformer as a functor. 

functor

4. OCaml Implementation

Cambridge L28 taught in 2014–2015 has, in its lecture notes, an implementation in OCaml which is very straightforward: 

module type MONAD =
sig
  type 'a t
  val return : 'a -> 'a t
  val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
end

module type STATE =
sig
  include MONAD
  type state
  val get : state t
  val put : state -> unit t
  val runState : 'a t -> init:state -> state * 'a
end

5. References

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

Last Updated 2023-02-14 Tue 10:48.