Monad transformer

The Wikibook Haskell has a page on the topic of: Monad transformers

In functional programming, a monad transformer is a type constructor which takes a monad as an argument and returns a monad as a result.

Monad transformers can be used to compose features encapsulated by monads - such as state, exception handling, and I/O - in a modular way. Typically, a monad transformer is created by generalising an existing monad; applying the resulting monad transformer to the identity monad yields a monad which is equivalent to the original monad (ignoring any necessary boxing and unboxing).

Definition

A monad transformer consists of:

1. A type constructor t of kind (* -> *) -> * -> *
2. Monad operations return and bind (or an equivalent formulation) for all t m where m is a monad, satisfying the monad laws
3. An additional operation, lift :: m a -> t m a, satisfying the following laws:^[1] (the notation `bind` below indicates infix application):
   1. lift . return = return
   2. lift (m `bind` k) = (lift m) `bind` (lift . k)

Examples

The option monad transformer

Given any monad ${\displaystyle \mathrm {M} \,A}$ , the option monad transformer ${\displaystyle \mathrm {M} \left(A^{?}\right)}$  (where ${\displaystyle A^{?}}$  denotes the option type) is defined by:

• ${\displaystyle \mathrm {return} :A\rightarrow \mathrm {M} \left(A^{?}\right)=a\mapsto \mathrm {return} (\mathrm {Just} \,a)}$ 
• ${\displaystyle \mathrm {bind} :\mathrm {M} \left(A^{?}\right)\rightarrow \left(A\rightarrow \mathrm {M} \left(B^{?}\right)\right)\rightarrow \mathrm {M} \left(B^{?}\right)=m\mapsto f\mapsto \mathrm {bind} \,m\,\left(a\mapsto {\begin{cases}{\mbox{return Nothing}}&{\mbox{if }}a=\mathrm {Nothing} \\f\,a'&{\mbox{if }}a=\mathrm {Just} \,a'\end{cases}}\right)}$ 
• ${\displaystyle \mathrm {lift} :\mathrm {M} (A)\rightarrow \mathrm {M} \left(A^{?}\right)=m\mapsto \mathrm {bind} \,m\,(a\mapsto \mathrm {return} (\mathrm {Just} \,a))}$ 

The exception monad transformer

Given any monad ${\displaystyle \mathrm {M} \,A}$ , the exception monad transformer ${\displaystyle \mathrm {M} (A+E)}$  (where ${\displaystyle E}$  is the type of exceptions) is defined by:

• ${\displaystyle \mathrm {return} :A\rightarrow \mathrm {M} (A+E)=a\mapsto \mathrm {return} (\mathrm {value} \,a)}$ 
• ${\displaystyle \mathrm {bind} :\mathrm {M} (A+E)\rightarrow (A\rightarrow \mathrm {M} (B+E))\rightarrow \mathrm {M} (B+E)=m\mapsto f\mapsto \mathrm {bind} \,m\,\left(a\mapsto {\begin{cases}{\mbox{return err }}e&{\mbox{if }}a=\mathrm {err} \,e\\f\,a'&{\mbox{if }}a=\mathrm {value} \,a'\end{cases}}\right)}$ 
• ${\displaystyle \mathrm {lift} :\mathrm {M} \,A\rightarrow \mathrm {M} (A+E)=m\mapsto \mathrm {bind} \,m\,(a\mapsto \mathrm {return} (\mathrm {value} \,a))}$ 

The reader monad transformer

Given any monad ${\displaystyle \mathrm {M} \,A}$ , the reader monad transformer ${\displaystyle E\rightarrow \mathrm {M} \,A}$  (where ${\displaystyle E}$  is the environment type) is defined by:

• ${\displaystyle \mathrm {return} :A\rightarrow E\rightarrow \mathrm {M} \,A=a\mapsto e\mapsto \mathrm {return} \,a}$ 
• ${\displaystyle \mathrm {bind} :(E\rightarrow \mathrm {M} \,A)\rightarrow (A\rightarrow E\rightarrow \mathrm {M} \,B)\rightarrow E\rightarrow \mathrm {M} \,B=m\mapsto k\mapsto e\mapsto \mathrm {bind} \,(m\,e)\,(a\mapsto k\,a\,e)}$ 
• ${\displaystyle \mathrm {lift} :\mathrm {M} \,A\rightarrow E\rightarrow \mathrm {M} \,A=a\mapsto e\mapsto a}$ 

The state monad transformer

Given any monad ${\displaystyle \mathrm {M} \,A}$ , the state monad transformer ${\displaystyle S\rightarrow \mathrm {M} (A\times S)}$  (where ${\displaystyle S}$  is the state type) is defined by:

• ${\displaystyle \mathrm {return} :A\rightarrow S\rightarrow \mathrm {M} (A\times S)=a\mapsto s\mapsto \mathrm {return} \,(a,s)}$ 
• ${\displaystyle \mathrm {bind} :(S\rightarrow \mathrm {M} (A\times S))\rightarrow (A\rightarrow S\rightarrow \mathrm {M} (B\times S))\rightarrow S\rightarrow \mathrm {M} (B\times S)=m\mapsto k\mapsto s\mapsto \mathrm {bind} \,(m\,s)\,((a,s')\mapsto k\,a\,s')}$ 
• ${\displaystyle \mathrm {lift} :\mathrm {M} \,A\rightarrow S\rightarrow \mathrm {M} (A\times S)=m\mapsto s\mapsto \mathrm {bind} \,m\,(a\mapsto \mathrm {return} \,(a,s))}$ 

The writer monad transformer

Given any monad ${\displaystyle \mathrm {M} \,A}$ , the writer monad transformer ${\displaystyle \mathrm {M} (W\times A)}$  (where ${\displaystyle W}$  is endowed with a monoid operation ${\displaystyle *}$  with identity element ${\displaystyle \varepsilon }$ ) is defined by:

• ${\displaystyle \mathrm {return} :A\rightarrow \mathrm {M} (W\times A)=a\mapsto \mathrm {return} \,(\varepsilon ,a)}$ 
• ${\displaystyle \mathrm {bind} :\mathrm {M} (W\times A)\rightarrow (A\rightarrow \mathrm {M} (W\times B))\rightarrow \mathrm {M} (W\times B)=m\mapsto f\mapsto \mathrm {bind} \,m\,((w,a)\mapsto \mathrm {bind} \,(f\,a)\,((w',b)\mapsto \mathrm {return} \,(w*w',b)))}$ 
• ${\displaystyle \mathrm {lift} :\mathrm {M} \,A\rightarrow \mathrm {M} (W\times A)=m\mapsto \mathrm {bind} \,m\,(a\mapsto \mathrm {return} \,(\varepsilon ,a))}$ 

The continuation monad transformer

Given any monad ${\displaystyle \mathrm {M} \,A}$ , the continuation monad transformer maps an arbitrary type ${\displaystyle T}$  into functions of type ${\displaystyle (T\rightarrow \mathrm {M} \,A)\rightarrow \mathrm {M} \,A}$ . It is defined by:

• ${\displaystyle \mathrm {return} \colon T\rightarrow \left(T\rightarrow \mathrm {M} \,A\right)\rightarrow \mathrm {M} \,A=t\mapsto f\mapsto f\,t}$ 
• ${\displaystyle \mathrm {bind} \colon \left(\left(T\rightarrow \mathrm {M} \,A\right)\rightarrow \mathrm {M} \,A\right)\rightarrow \left(T\rightarrow \left(T'\rightarrow \mathrm {M} \,A\right)\rightarrow \mathrm {M} \,A\right)\rightarrow \left(T'\rightarrow \mathrm {M} \,A\right)\rightarrow \mathrm {M} \,A}$ ${\displaystyle =c\mapsto f\mapsto k\mapsto c\,\left(t\mapsto f\,t\,k\right)}$ 
• ${\displaystyle \mathrm {lift} :\mathrm {M} \,T\rightarrow (T\rightarrow \mathrm {M} \,A)\rightarrow \mathrm {M} \,A=m\mapsto \mathrm {bind} \,m}$ 

Note that monad transformations are not commutative: for instance, applying the state transformer to the option monad yields a type ${\displaystyle S\rightarrow \left(A\times S\right)^{?}}$  (a computation which may fail and yield no final state), whereas the converse transformation has type ${\displaystyle S\rightarrow \left(A^{?}\times S\right)}$  (a computation which yields a final state and an optional return value).

See also

• Monads in functional programming
• Natural transformation - a related concept in category theory

References

1. Liang, Sheng (1995). "Monad transformers and modular interpreters" (PDF). Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, NY: ACM. pp. 333–343. doi:10.1145/199448.199528. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)

External links

• [1] - a highly technical blog post briefly reviewing some of the literature on monad transformers and related concepts, with a focus on categorical-theoretic treatment