ianhenderson.org / 2025 may 1
Let's start with the simplest example.
struct Id<T> {
value: T
}
def pure(a: T) -> Id<T> {
Id<T>{ value: a }
}
def bind(a: Id<T>, f: T -> Id<U>) -> Id<U> {
f(a.value)
}
An Id<T> wraps a single value of type T. Since it has a pure function and a bind function with the proper type signatures, it can be used with do.
def addOne(a: Int) -> Id<Int> {
Id<T>{ value: a + 1 }
}
def addThree(a: Int) -> Id<Int> {
do {
b <- addOne(a)
c <- addOne(b)
d <- addOne(c)
return d
}
}
To expand out the do notation, each <- becomes a call to bind, and each return becomes a call to pure.
def addOne(a: Int) -> Id<Int> {
Id<T>{ value: a + 1 }
}
def addThree(a: Int) -> Id<Int> {
bind(addOne(a), |b| {
bind(addOne(b), |c| {
bind(addOne(c), |d| {
pure(d)
})
})
})
}
If you substitute all the function calls for their implementations, you can see this does produce a wrapped version of a with three added to it, though in a pretty roundabout way. Values are wrapped in addOne, then unwrapped again in bind to pass to the next function.
To avoid the final step of wrapping and unwrapping, you can put the last call on its own line rather than using return—this will use the return value of the last call directly without unwrapping the value using bind and passing it to pure to be wrapped again. That is,
def addThree(a: Int) -> Id<Int> {
do {
b <- addOne(a)
c <- addOne(b)
addOne(c)
}
}
becomes
def addThree(a: Int) -> Id<Int> {
bind(addOne(a), |b| {
bind(addOne(b), |c| {
addOne(c)
})
})
}
To allow this sort of simplification in general, it's usually a good idea to implement pure and bind in a way that bind(a, |b| { pure(b) }) is equal to a.
Now let's look at a more interesting example, Log<T>.
struct Log<T> {
value: T
log: List<String>
}
def pure(a: T) -> Log<T> {
Log<T>{ value: a, log: [] }
}
def bind(a: Log<T>, f: T -> Log<U>) -> Log<U> {
let b = f(a.value)
Log<T>{ value: b.value, log: append(a.log, b.log) }
}
The Log<T> type adds a new field, log, which collects a list of Strings. In bind, the logs produced from calling the function f with the unwrapped value are appended to the logs already recorded in the Log<T>.
If you extend the addOne function to also log what it's doing, it's just as easy to chain these functions together using do as it was in the earlier version without logging.
def addOneAndLog(a: Int) -> Log<Int> {
Log<T>{
value: a + 1
log: ["added one to ${a}"]
}
}
def addThreeAndLog(a: Int) -> Log<Int> {
do {
b <- addOneAndLog(a)
c <- addOneAndLog(b)
addOneAndLog(c)
}
}
This expands out in the same way as before:
def addOneAndLog(a: Int) -> Log<Int> {
Log<T>{
value: a + 1
log: ["added one to ${a}"]
}
}
def addThreeAndLog(a: Int) -> Log<Int> {
bind(addOneAndLog(a), |b| {
bind(addOneAndLog(b), |c| {
addOneAndLog(c)
})
})
}
…and if you fully substitute all the function calls, you can see the result will be Log<T>{ value: a + 3, log: ["added one to ${a}", "added one to ${a + 1}", "added one to ${a + 2}"] }.
This is the power of do notation: it lets you encapsulate many kinds of state tracking and control flow behind the interface of pure and bind. This includes enforcing rules that may not be available in the type system of the language itself. The original motivation behind do was to support I/O in Haskell, which evaluates functions "lazily" as their results are demanded. If you do print("hello") and then print("world"), you need some way to get the two operations to actually run, and to run in the right order.
One way to solve this is to introduce a type called RealWorld. There's only one RealWorld value at a time—conceptually, each I/O function consumes the old world and produces a new one where the I/O has happened.
def print(msg: String, world: RealWorld) -> RealWorld
def input(world: RealWorld) -> (RealWorld, String)
To run the program, the last RealWorld value is demanded, which requires running the last function, which then demands the RealWorld it receives as an argument, eventually running the entire program in sequence.
The problem with this, in Haskell, is that references to an old RealWorld could have been stored somewhere even after being passed to an I/O function. If an old reference is reused, it could lead to I/O operations never happening, happening out of order, or getting interleaved with each other. Other languages like Clean have a type system feature called uniqueness types that provides the proper guarantees, but Haskell doesn't have this feature.
But what if you make the RealWorld private and export only a type IO<T> with pure and bind?
struct IO<T> {
run: RealWorld -> (RealWorld, T)
}
def pure(a: T) -> IO<T> {
IO<T>{
run: |w| {
(w, a)
}
}
}
def bind(a: IO<T>, f: T -> IO<U>) -> IO<U> {
IO<T>{
run: |w_old| {
let (w_new, b) = a.run(w_old) // assume let is strict here, unlike Haskell's let
f(b).run(w_new)
}
}
}
All the references to RealWorld values occur within the run function. Both pure and bind use each RealWorld value once and only once. The IO<T> values themselves don't hold any references to RealWorld values—they contain only a function waiting to accept a RealWorld value in the future. So, assuming the only external interface to IO is an opaque IO<T> type and the pure and bind functions, the uniqueness rule is guaranteed to be followed.
It's also worth mentioning that once you've made the IO type opaque, the RealWorld trick is just an implementation detail. Not all Haskell implementations use RealWorld values internally. The semantics of IO under pure and bind are the important things, not the way those semantics are implemented.
In any case, I/O functions can be written to return IO<T> values, making it easy to chain them together with do notation.
def print(msg: String) -> IO<Unit> { ... }
def input() -> IO<String> { ... }
def sayName() -> IO<Unit> {
do {
_ <- print("What's your name?")
name <- input()
print("Hello, ${name}!")
}
}
In most languages with do (including Haskell), you can leave out the _ <- for values like print("What's your name?") which you don't need to bind the result of.
def print(msg: String) -> IO<Unit> { ... }
def input() -> IO<String> { ... }
def sayName() -> IO<Unit> {
do {
print("What's your name?")
name <- input()
print("Hello, ${name}!")
}
}
To support this notation, a third function,
allows two values to be sequenced without creating an intermediate function. The above do notation expands out to use then.
def print(msg: String) -> IO<Unit> { ... }
def input() -> IO<String> { ... }
def sayName() -> IO<Unit> {
then(print("What's your name?"),
bind(input(), |name| {
print("Hello, ${name}!")
})
)
}
In Haskell, bind is called >>=, then is called >>, and pure is called return. A type becomes buildable using do notation by becoming an instance of the Monad typeclass, which involves implementing these three functions.