```
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE EmptyCase #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE IncoherentInstances #-}
```

# Algebraic Effects and Handlers in Haskell

# Introduction

Algebraic effects and handlers are a popular technique for modeling and implementing side effects.
A key idea behind the technique is to define effects as interfaces of effectful operations such that we can program against these interfaces, and provide independent implementations of these interfaces later.
This blog post explains how to model algebraic effects in Haskell.
In part two and part three of the blog post we show how these techniques scale to model a broader class of effects than algebraic effects, namely *higher-order effects*.

The focus of the blog post series is to explain how to model and implement effects in a typed and conceptually clear way. There are excellent Haskell libraries available on Hackage that provide more efficient and (for many purposes) more ergonomic implementations of algebraic effects.

### Contents

# Representing Programs and Effect Interfaces

An algebraic effect is essentially an interface comprising a set of related operations.
Programs written against such interfaces are represented as abstract syntax trees whose nodes represent effectful operations.
These syntax trees are given by the following data type, commonly known as *the free monad*^{1} where `Pure`

represents a value, and `Op`

represents an operation given by a *signature functor* `f`

:

```
data Free f a
= Pure a
| Op (f (Free f a))
```

For a signature functor `f :: * -> *`

, the type `f k`

encodes the syntax of an operation whose *continuation* (the remaining computation after the operation) is a program of type `k`

.
So the application of `f`

to `(Free f a)`

in `Op (f (Free f a))`

represents an operation whose continuation is itself a syntax tree of type `Free f a`

.

For example, consider the following signature functor of two stateful operations:

```
data State s k
= Put s k
| Get (s -> k)
deriving Functor
```

We can think of this signature functor as an interface that defines a `Put`

and a `Get`

operation.
Using this, `Free (State s) s`

is the type sequences of `Put`

and `Get`

operations which eventually return an `s`

value, such as the following program which increments an integer state and returns the value of the state before the increment:

```
preinc :: Free (State Int) Int
= Op (Get (\s -> Op (Put (s + 1) (Pure s)))) preinc
```

Writing programs against more than one interface is also possible, using *functor sums*.

```
infixr 6 +
data (f + g) a
= L (f a)
| R (g a)
deriving Functor
```

For example, say we have another signature functor `Err`

representing abrupt termination.

```
data Err k = Err String
deriving Functor
```

Since `Err`

operations abruptly terminate, the syntax of an `Err`

operation does not have any continuation; i.e., it does not use its parameter `k`

.

The following program uses both the `State`

and `Err`

interfaces, and uses an “empty” signature functor `End`

to mark the end of an effect row:

```
data End k -- No constructors!
deriving Functor
incerr :: Free (Err + State Int + End) a
= Op (R (L (Get (\s ->
incerr Op (R (L (Put (s + 1)
Op (L (Err "foo")))))))))) (
```

But this program is hard to write and hard to read.
To make programs easier to read and write, we make use of (standard) infrastructure which lets us write `incerr`

like this instead:

```
incerr' :: Free (State Int + Err + End) a
= do s <- get; put (s + 1); err "foo" incerr'
```

We borrow the needed infrastructure from Data Types à la Carte.

## Signature Subtyping

Signature subtyping `f < g`

witnesses that we can transform any `f k`

into a `g k`

; i.e.:

```
class f < g where
inj :: f k -> g k
```

In particular, we have the following three instances:

```
instance f < f where inj = id
instance f < (f + g) where inj = L
instance f < h => f < (g + h) where inj = R . inj
```

## Smart Constructors

We use signature subtyping to automatically inject an effect into a larger set of effects; e.g.:

```
get :: State s < f => Free f s
= Op (inj (Get Pure))
get
put :: State s < f => s -> Free f ()
= Op (inj (Put s (Pure ())))
put s
err :: Err < f => String -> Free f a
= Op (inj (Err msg)) err msg
```

## Monadic Bind

We can sequence computations in general and smart constructors in particular using the monadic bind of `Free`

.

To do so in Haskell we also need to provide a `Functor`

and `Applicative`

instance for `Free`

.

Everything is given by a fold over `Free`

:

```
instance Functor f => Monad (Free f) where
>>= k = fold k Op m
m
instance Functor f => Functor (Free f) where
fmap f = fold (pure . f) Op
instance Functor f => Applicative (Free f) where
pure = Pure
<*> m = fold (flip fmap m) Op f f
```

Using this monad instance and our smart constructors, our refined `incerr'`

program is now much simpler and nicer to read and write:

```
incerr' :: Free (Err + State Int + End) a
= do (s :: Int) <- get; put (s + 1); err "foo" incerr'
```

The `(s :: Int)`

is a type hint that aids Haskell’s type checker in satisfying the type class constraint of the smart constructors for `put`

and `get`

.

# Implementing Effect Interfaces by Effect Handling

We give meaning to programs written against effect interfaces by handling their effects.
The idea is to define handlers for specific effects such as `State`

or `Err`

independently.
By applying these handlers in a nested fashion we can provide implementations of the effect interfaces that programs use, such that we can run the program.

An *effect handler* of type `Handler f a f' b`

handles effects `f`

, leaving behind effects `f'`

, and transforms the return type of a computation from `a`

to `b`

:

```
handle :: (Functor f, Functor f')
=> Handler f a g b -> Free (f + f') a -> Free f' b
```

The `handle`

function is defined in terms of a `fold`

over `Free`

:

```
fold :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
Pure x) = gen x
fold gen _ (Op f) = alg (fmap (fold gen alg) f) fold gen alg (
```

Here `fold gen alg`

uses (1) a `gen`

erator function `(a -> b)`

to generate `b`

values from `Pure a`

values, and (2) an `alg`

ebra `(f b -> b)`

which transforms a constructor of a signature functor `f`

into a `b`

, assuming the continuation(s) of `f`

have been folded into `b`

s already.

A `Handler`

is then given by a record comprising two functions: `ret`

, the generator of a fold; and `hdlr`

, the algebra of a fold:

```
data Handler f a f' b
= Handler { ret :: a -> Free f' b
hdlr :: f (Free f' b) -> Free f' b }
,
handle :: (Functor f, Functor f')
=> Handler f a f' b -> Free (f + f') a -> Free f' b
= fold
handle h
(ret h)-> case x of
(\x L y -> hdlr h y
R y -> Op y)
```

The `handle`

function assumes that `f`

is the first effect occurring in an effect sum. However, since sums are associative and commutative, handlers can be applied in any order in practice.

```
infixr 5 ->:
type (f ->: g) = forall a. f a -> g a
assocSum :: f + (g + h) ->: (f + g) + h
L x) = L (L x)
assocSum (R (L x)) = L (R x)
assocSum (R (R x)) = R x
assocSum (
commSum :: f + g ->: g + f
L x) = R x
commSum (R x) = L x
commSum (
permute :: (Functor f, Functor f')
=> (f ->: f') -> Free f a -> Free f' a
= fold Pure (Op . f) permute f
```

The handler of the `Err`

effect is:

```
hErr :: Functor f' => Handler Err a f' (Either String a)
= Handler
hErr = pure . Right
{ ret = \x -> case x of Err s -> pure (Left s) } , hdlr
```

In the `ret`

urn case, we have reached a `Pure`

value at the end of a computation, and we can simply return a value wrapped in `Right`

, indicating that no error was raised.
In the `hdlr`

case, we raise an error by returning an error message (a `String`

) wrapped in `Left`

.

In order to handle the `State`

effect, we will introduce a more general handler type which passes a stateful parameter along during handling.

```
data Handler_ f a p f' b
= Handler_ { ret_ :: a -> (p -> Free f' b)
hdlr_ :: f (p -> Free f' b) -> (p -> Free f' b) }
,
handle_ :: (Functor f, Functor f')
=> Handler_ f a p f' b -> Free (f + f') a
-> p -> Free f' b
= fold
handle_ h
(ret_ h)-> case x of
(\x L x -> hdlr_ h x
R x -> \p -> Op (fmap (\m -> m p) x))
```

Using this, the handler of `State`

is:

```
hState :: Functor g => Handler_ (State s) a s g (a, s)
= Handler_
hState = \x s -> pure (x, s)
{ ret_ = \x s -> case x of
, hdlr_ Put s' k -> k s'
Get k -> k s s }
```

In the `ret_`

case, we return a pair of a value and the current (final) state.
In the `hdlr_`

case, we either pass a new state value to the continuation of a `Put`

operation; or, in case of a `Get`

operation, we pass the current state value to the continuation twice: both as an argument and as the current, unchanged state.

Now, using the `un`

function

```
un :: Free End a -> a
Pure x) = x
un (Op f) = case f of un (
```

we give meaning to our `incerr'`

program written against the `hState`

and `hErr`

interfaces:

`0) == (Left "foo", 1) un (handle_ hState (handle hErr incerr') `

A key property of algebraic effects and handlers is that we can change the interface implementations of `incerr'`

without changing the program itself.

For example, we can use a `hState'`

handler which returns a stream of the states seen during evaluation:

```
hState' :: Functor g => Handler_ (State s) a [s] g (a, [s])
= Handler_
hState' = \x ss -> pure (x, ss)
{ ret_ = \x ss -> case x of
, hdlr_ Put s' k -> k (s':ss)
Get k -> k (head ss) ss }
```

Now:

`0]) == (Left "foo", [1, 0]) un (handle_ hState' (handle hErr incerr') [`

# Beyond Algebraic Effects

There are many more examples of algebraic effects than the two simple state and error effects discussed in this blog post. For example, non-deterministic choice and even continuations can be modeled using algebraic effects and handlers.

However, some effects are awkward to model using algebraic effects and handlers alone. Particularly higher-order effects; that is, effects with one or more operations that have one or more parameters of a computation type. Such higher-order effects are commonly found in Haskell’s popular monad transformer library, mtl.

For example, the `local`

effect of the reader monad whose interface is summarized by the following type class:^{2}

```
class Monad m => MonadReader r m | m -> r where
ask :: m r
local :: (r -> r) -> m a -> m a
-- ^^^ computation typed parameter
```

Consider how we might define `Reader`

in terms of a signature functor.

```
data Reader r k
= Ask (r -> k)
| forall a. Local (r -> r) (X a) (a -> k)
```

The key question is: what is `X`

here?

To match the `MonadReader`

type class interface, it should be a syntax tree with the same effects as `k`

.
The problem is that `Free`

does not support signature functors that capture this type constraint!
Luckily, there is a relatively simple solution to this problem: if we generalize `Free`

to use *higher-order functors* rather than plain functors for signatures, we capture precisely this constraint.

But that still leaves open the question of how to implement higher-order effect interfaces. In part two, we show how we can emulate higher-order effect interfaces using only algebraic effects and handlers, by adapting the infrastructure in this blog post a little. However, the solution in part two does not let us modularly change the higher-order effect interface implementations without changing or recompiling the programs written against them. In part three, we provide a more principled solution.