Monad transformers, Free, Tagless final

The algebraic hierarchy gives you individual effects (Maybe, Either, State, Reader, Writer, IO) but doesn't tell you how to combine them — what if a computation can fail and read from an environment and log? You need a stack of effects. There are three classical answers, each fixing the problems of the last: monad transformers, free monads, and tagless final.

The problem: monads don't naturally compose

Given two monads M and N, the type M (N a) is not in general a monad. Maybe (List a) doesn't compose cleanly: there's no canonical way to join an Maybe (List (Maybe (List a))). That's the gap each technique fills, differently.

1 · Monad transformers

A monad transformer T turns a monad M into a richer monad T M. Each effect ships with its transformer:

You stack them: StateT s (ExceptT e IO) a is "a computation that has state s, can fail with e, performs IO, and produces a."

Cost: lift boilerplate (you must hoist inner-monad actions through the stack), and the order of the stack matters semantically — StateT s (ExceptT e Identity) rolls back state on error, while ExceptT e (StateT s Identity) keeps it.

This is the mtl style in Haskell, and the dominant pattern through the 2010s.

2 · Free monads

A free monad turns any functor F into a monad — for free. The trick: represent your program as a tree of effects without running them, then interpret the tree later.

data Free f a = Pure a | Roll (f (Free f a))

You define your effect language as an algebraic data type:

data ConsoleF a = GetLine (String -> a) | PutLine String a
type Console = Free ConsoleF

prog :: Console ()
prog = do
  n <- getLine
  putLine ("hello " ++ n)

prog is a value — a tree describing the program. You then write interpreters:

• runIO :: Console a → IO a (the real interpreter)
• runPure :: [String] → Console a → ([String], a) (test interpreter with mocked input)

Win: clean separation of what the program does from how it runs; trivially testable; you can analyze the tree (count effects, optimize).

Cost: runtime overhead from building and walking trees; cumbersome for deep effect stacks (the famous n² problem when combining many algebras).

3 · Tagless final

The tagless final style encodes the effect language not as data but as a typeclass / interface. The program is polymorphic in the carrier monad:

class Monad m => Console m where
  getLine' :: m String
  putLine' :: String -> m ()

prog :: Console m => m ()
prog = do
  n <- getLine'
  putLine' ("hello " ++ n)

You write multiple instances: instance Console IO, instance Console TestM, etc. The program is the same code; you swap interpreters by choosing the monad at the call site.

Win: zero runtime overhead (no tree, just function calls); composes better than mtl for big effect sets; easy to mock.

Cost: requires higher-rank type machinery in Haskell; harder to inspect/optimize a program (no data, just behavior).

Which one when?

Clojure analog

Clojure doesn't use any of these directly — its idiom is just pass maps around, with dynamic vars for "ambient" effects. But the idea of tagless final shows up clearly in:

• Protocols as effect interfaces: pass an IO protocol around, swap implementations for tests.
• component / integrant — explicitly threading the effect stack rather than smuggling it through types.

That's tagless final in Clojure clothing.

Real-world: which approach where

The migration arc in industry has been: mtl → tagless-final → algebraic effects. Each step reduces boilerplate while keeping the "describe vs interpret" split. Clojure skipped the whole journey by passing maps and using protocols — different ergonomics, similar end result.

Check yourself

Exercise

Sketch (in pseudo-code or Haskell) the same readConfigAndIncrement program three ways: as an mtl stack ReaderT Config (State Int), as a free monad with a ConfigF | StateF functor, and as a tagless-final program polymorphic in (MonadReader Config m, MonadState Int m). Compare the boilerplate vs flexibility.