Comparison of prompt and free monads

00-MonadPrompt.md

Comparison of prompt and free monads.

Summary

The prompt monad is a free monad but with a more convenient programming interface in the context of designing EDSLs. It also predates free monads as far as the Haskell community is concerned.

Context

Type names refer to the MonadPrompt and free packages on Hackage.

Usage

For Prompt, one defines an API GADT API r where each constructor takes the parameters of an API function as arguments, and specifies its result type in r. In contrast, for Free, one needs to define a functor; each constructor takes the arguments of an API function as parameters, and in addition a continuation that is a function from the result type to a value of th functor's argument type. See ExPrompt and ExFree for examples. Note that the Prompt code is slightly less cluttered and thus a bit simpler. So for implmenting EDSLs, which are usually thought of as an API, prompt monads are more convenient.

Relation between prompt and free monads

Both Prompt and Free are universal monad. Basically, Prompt p a is isomorphic to Free (PromptF p) a where

data PromptF p a where
    PromptF :: p r -> (r -> a) -> PromptF p a

Similarly, Free f a is isomorphic to Prompt (FreeP f) a where

data FreeP f a where
    FreeP :: f a -> FreeP f a

This is elaborated in Free2Prompt and Prompt2Free2.

Historic note

As far as I know, the arrival of MonadPrompt predates the popularization of free monads in the Haskell community by a couple of months, see the links below. In fact, some early discussion on the topic of universality revolved around a universal monad called Unimo that has long been forgotten, rather than free monads.

Links

• original description (Ryan Ingram, 2007-11-18)
• continuations (apfelmus + Bertram Felgenhauer, 2008-01-18)
• discussion of Unimo (but there was more, leading up to MonadPrompt's RecPrompt type to capture continuations)
• MonadPrompt (Hackage, uploaded 2008-03-20)
• Monads for Free (Comonad reader, 2008-04-11)
• free (Hackage, uploaded 2011-02-17)
• free monads are free (There must be a better link)

ExFree.hs

-- mini-EDSL using `free`

{-# LANGUAGE DeriveFunctor #-}

module ExFree where

import qualified Control.Monad.Free as F
import qualified Control.Monad.State as S

-- First we define the API. What is `a`?
data DSL a
    = Put Int a
    | Get (Int -> a)
  deriving Functor

-- The operations. `F.Free` on the outside, `F.Pure` on the inside.
put :: Int -> F.Free DSL ()
put i = F.Free (Put i (F.Pure ()))

get :: F.Free DSL Int
get = F.Free (Get F.Pure)

-- For execution, we treat the constructors of `DSL` that involve `a`
-- as continuations.
run :: F.Free DSL a -> Int -> a
run program i = S.evalState (F.iterM step program) i
  where
    step :: DSL (S.State Int a) -> S.State Int a
    step (Put i cnt) = S.put i >> cnt
    step (Get cnt)   = S.get >>= cnt

-- | test
-- > (42,23)
test :: (Int, Int)
test = run prog 42
  where
   prog = do
      i <- get
      put 23
      v <- get
      return (i,v)

ExPrompt.hs

-- mini-EDSL using `MonadPrompt`

{-# LANGUAGE GADTs #-}

module ExPrompt where

import qualified Control.Monad.Prompt as P
import qualified Control.Monad.State as S

-- First define the API as a GADT. `r` is the result type of the operation.
data DSL r where
    Put :: Int -> DSL ()
    Get :: DSL Int

-- The operations are just invocations of `P.prompt`
put :: Int -> P.Prompt DSL ()
put i = P.prompt (Put i)

get :: P.Prompt DSL Int
get = P.prompt Get

-- And for executing, we can implement each operation in a natural way.
run :: P.Prompt DSL a -> Int -> a
run program i = S.evalState (P.runPromptM step program) i
  where
    step :: DSL a -> S.State Int a
    step (Put i) = S.put i
    step Get     = S.get

-- | test
-- > (42,23)
test :: (Int, Int)
test = run prog 42
  where
    prog = do
        i <- get
        put 23
        v <- get
        return (i,v)

Free2Prompt.hs

-- `Prompt` in terms of `Free`

{-# LANGUAGE GADTs #-}
{-# LANGUAGE RankNTypes #-}

module Free2Prompt where

import qualified Control.Monad.Free as F
import qualified Control.Monad.State as S -- for the example

-- The following functor corresponds to a prompt `p`.
-- Its values consist of a prompt value and a continuation.
data PromptF p a where
    PromptF :: p r -> (r -> a) -> PromptF p a

instance Functor (PromptF p) where
    fmap f (PromptF p cont) = PromptF p (f . cont)

-- `Prompt` can now be expressed in terms of `F.Free`.
type Prompt p a = F.Free (PromptF p) a

-- `prompt` simply uses `F.Pure` as the continuation
prompt :: p r -> Prompt p r
prompt p = F.Free (PromptF p F.Pure)

-- When running an action, `step` is executed on the prompt,
-- and the result is passed to the continuation.
runPromptM :: Monad m => (forall a. p a -> m a) -> Prompt p r -> m r
runPromptM step = F.iterM step'
  where
    step' (PromptF p cnt) = step p >>= cnt

------------------------------------------------------------------------------
-- The following is included from `ExPrompt.hs` with minor adaptations:
-- `P.Prompt` -> `Prompt`, `P.prompt` -> `prompt`

-- mini-EDSL using `MonadPrompt`

-- First define the API as a GADT. `r` is the result type of the operation.
data DSL r where
    Put :: Int -> DSL ()
    Get :: DSL Int

-- The operations are just invocations of `P.prompt`
put :: Int -> Prompt DSL ()
put i = prompt (Put i)

get :: Prompt DSL Int
get = prompt Get

-- And for executing, we can implement each operation in a natural way.
run :: Prompt DSL a -> Int -> a
run program i = S.evalState (runPromptM step program) i
  where
    step :: DSL a -> S.State Int a
    step (Put i) = S.put i
    step Get     = S.get

-- | test
-- > (42,23)
test :: (Int, Int)
test = run prog 42
  where
    prog = do
        i <- get
        put 23
        v <- get
        return (i,v)

Prompt2Free.hs

-- `Free` in terms of `Prompt`

{-# LANGUAGE GADTs #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE DeriveFunctor #-} -- for the example

module Prompt2Free where

import qualified Control.Monad.Prompt as P
import Control.Monad
import qualified Control.Monad.State as S -- for the example

-- The following prompt corresponds to the functor `f` applied to `a`.
--
-- Note that the `a` type has lost its meaning as a result type of each
-- operation; instead, `a` will be the leaf type of the computation
-- tree, whatever that turns out to be.
data FreeP f a where
    FreeP :: f a -> FreeP f a

-- `Free` can now be expressed in terms of `P.Prompt`.
type Free f a = P.Prompt (FreeP f) a

-- `free` replaces the `Free` constructor; `pure` replaces `Pure`.
free :: f (Free f a) -> Free f a
free f = join (P.prompt (FreeP f))

-- Running an action applies `pure` on the leafs, `step` on the outside,
-- but first has to reduce the inside; this cannot be expressed directly
-- with `runPromptM`, but `runPromptC` is powerful enough.
iterM :: forall m f a. (Monad m, Functor f) => (f (m a) -> m a) -> Free f a -> m a
iterM step p = P.runPromptC pure step' p
  where
    step' :: FreeP f b -> (b -> m a) -> m a
    step' (FreeP f) cnt = step (cnt <$> f)

------------------------------------------------------------------------------
-- The following is included from `ExFree.hs` with minor adaptations:
-- `F.Free` -> `Free`, `F.Pure` -> `pure`, `F.Free` -> `free`.

-- mini-EDSL using `Free`

-- First we define the API. What is `a`?
data DSL a
    = Put Int a
    | Get (Int -> a)
  deriving Functor

-- The operations. `F.Free` on the outside, `F.Pure` on the inside.
put :: Int -> Free DSL ()
put i = free (Put i (pure ()))

get :: Free DSL Int
get = free (Get pure i)

-- For execution, we treat the constructors of `DSL` that involve `a`
-- as continuations.
run :: Free DSL a -> Int -> a
run program i = S.evalState (iterM step program) i
  where
    step :: DSL (S.State Int a) -> S.State Int a
    step (Put i cnt) = S.put i >> cnt
    step (Get cnt)   = S.get >>= cnt

-- | test
-- > (42,23)
test :: (Int, Int)
test = run prog 42
  where
   prog = do
      i <- get
      put 23
      v <- get
      return (i,v)