{-# 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. The idea is to define effects as interfaces of effectful operations that we can program against, and that we can provide implementations of 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 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 containing 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¹ 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
preinc = Op (Get (\s -> Op (Put (s + 1) (Pure s))))

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
incerr =  Op (R (L (Get (\s ->
            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
incerr' = do s <- get; put (s + 1); err "foo"

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
get = Op (inj (Get Pure))

put  :: State s < f => s -> Free f ()
put s = Op (inj (Put s (Pure ())))

err :: Err < f => String -> Free f a
err msg = Op (inj (Err msg))

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

Before considering the monadic bind, we first consider the fold of the free monad.

Folding Over Free

The following function lets us fold any syntax tree of operations Free f a into some type b:

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

Here fold gen alg uses (1) a generator function (a -> b) to generate b values from Pure a values, and (2) an algebra (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 bs already.

Monadic Bind

We can use the fold function above to define 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
  m >>= k = fold k Op m

instance Functor f => Functor (Free f) where
  fmap f = fold (pure . f) Op

instance Functor f => Applicative (Free f) where
  pure = Pure
  f <*> m = fold (flip fmap m) Op 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
incerr' = do (s :: Int) <- get; put (s + 1); err "foo"

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:

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
handle h = fold
  (ret h)
  (\x -> case x of
     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
assocSum (L x) = L (L x)
assocSum (R (L x)) = L (R x)
assocSum (R (R x)) = R x

commSum :: f + g ->: g + f
commSum (L x) = R x
commSum (R x) = L x

permute :: (Functor f, Functor f')
        => (f ->: f') -> Free f a -> Free f' a
permute f = fold Pure (Op . f)

The handler of the Err effect is:

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

In the return 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
handle_ h = fold
  (ret_ h)
  (\x -> case x of
     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)
hState = Handler_
  { ret_ = \x s -> pure (x, s)
  , hdlr_ = \x s -> case x of
      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
un (Pure x) = x
un (Op f) = case f of

we give meaning to our incerr' program written against the hState and hErr interfaces:

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

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])
hState' = Handler_
  { ret_ = \x ss -> pure (x, ss)
  , hdlr_ = \x ss -> case x of
      Put s' k -> k (s':ss)
      Get k -> k (head ss) ss }

Now:

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

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:²

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.