Skip to content

Instantly share code, notes, and snippets.

@int-e
Last active April 6, 2021 23:21
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Embed
What would you like to do?
Comparison of prompt and free monads

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

-- 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)
-- 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)
-- `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)
-- `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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment