Free Monads and Effect Systems

42.1 Free Monads

Freer monads and tagless final (type class-based: class Monad m => MonadKV m where ...) are alternative styles for separating "what" from "how".

{-# LANGUAGE DeriveFunctor #-}
import Control.Monad.Free

-- 1. Define the instruction set as a Functor
data KVStoreF next
  = Put String String next
  | Get String (Maybe String -> next)
  | Delete String next
  deriving Functor

type KVStore = Free KVStoreF

-- 2. Smart constructors
put' :: String -> String -> KVStore ()
put' k v = liftF (Put k v ())
get' :: String -> KVStore (Maybe String)
get' k = liftF (Get k id)
delete' :: String -> KVStore ()
delete' k = liftF (Delete k ())

-- 3. Programs are pure data
program :: KVStore (Maybe String)
program = do
  put' "name" "Ana"
  put' "lang" "Haskell"
  delete' "name"
  get' "lang"

-- 4. Interpreters give them meaning
runPure :: KVStore a -> [(String, String)] -> (a, [(String, String)])
runPure (Pure a) s = (a, s)
runPure (Free (Put k v next)) s = runPure next ((k, v) : filter ((/= k) . fst) s)
runPure (Free (Get k cont)) s = runPure (cont (lookup k s)) s
runPure (Free (Delete k next)) s = runPure next (filter ((/= k) . fst) s)

runIO :: KVStore a -> IO a
runIO = iterM step
  where
    step (Put k v next) = putStrLn ("PUT " ++ k ++ "=" ++ v) >> next
    step (Get k cont) = putStrLn ("GET " ++ k) >> cont Nothing
    step (Delete k ne
…

42.2 Effect Systems

Type classes over transformer stacks (classic, fast, n² instances problem)

ReaderT-IO-based, fast, good ergonomics (Eff '[State Int, Error String, IOE] a)

Freer-monad-based, flexible higher-order effects (slower) Carrier-based, fast cleff, bluefin

Newer designs (bluefin: effects as value-level handles) Tagless final

Plain type classes with interpreters as instances

-- effectful example
{-# LANGUAGE DataKinds, TypeOperators #-}
import Effectful
import Effectful.State.Static.Local
import Effectful.Error.Static

counter :: (State Int :> es, Error String :> es) => Eff es Int
counter = do
  modify (+ 1)
  n <- get
  if n > 3 then throwError "too big" else pure n

-- runPureEff (runErrorNoCallStack (evalState 0 counter)) == Right 1