Concept:
Writer monad
Headline
A monad for synthesizing results or output
Illustration
Let us put to work the writer monad in a simple interpreter.
A baseline interpreter
There are these expression forms:
-- Simple Boolean expressions
data Expr = Constant Bool | And Expr Expr | Or Expr Expr
deriving (Eq, Show, Read)
For instance, the following expression should evaluate to true:
-- A sample term with two operations
sample = And (Constant True) (Or (Constant False) (Constant True))
Here is a simple interpreter, indeed:
-- A straightforward interpreter
eval :: Expr -> Bool
eval (Constant b) = b
eval (And e1 e2) = eval e1 && eval e2
eval (Or e1 e2) = eval e1 || eval e2
Adding counting to the interpreter
Now suppose that the interpreter should also return the number of operations applied. We count And and Oras operations. Thus, the sample term should count as 2. We may incorporate counting into the initial interpreter as follows:
-- Interpreter with counting operations
eval' :: Expr -> (Bool, Int)
eval' (Constant b) = (b, 0)
eval' (And e1 e2) =
let
(b1,i) = eval' e1
(b2,i') = eval' e2
in (b1 && b2, i+i'+1)
eval' (Or e1 e2) =
let
(b1,i) = eval' e1
(b2,i') = eval' e2
in (b1 || b2, i+i'+1)
Alas, the resulting interpreter is harder to understand. The collection of counts is entangled with the basic logic.
Monadic style
By conversion to monadic style, we can hide counting except when we need increment the counter. We use the Writer monad here so that we simply combine counts from subexpression (as also done in the non-monadic code above). We could also be using the state monad, if we wanted to really track the operations counter along evaluation; this would be useful if we were adding an expression form for retrieving the count.
evalM :: Expr -> Writer (Sum Int) Bool
evalM (Constant b) = return b
evalM (And e1 e2) =
evalM e1 >>= \b1 ->
evalM e2 >>= \b2 ->
tell (Sum 1) >>
return (b1 && b2)
evalM (Or e1 e2) =
evalM e1 >>= \b1 ->
evalM e2 >>= \b2 ->
tell (Sum 1) >>
return (b1 || b2)
We can also use do notation:
-- Monadic style interpreter in do notation
evalM :: Expr -> Writer (Sum Int) Bool
evalM (Constant b) = return b
evalM (And e1 e2) = do
b1 <- evalM e1
b2 <- evalM e2
tell (Sum 1)
return (b1 && b2)
evalM (Or e1 e2) = do
b1 <- evalM e1
b2 <- evalM e2
tell (Sum 1)
return (b1 || b2)
The Writer monad
The Writer monad is readily provided by the Haskell library (in Control.Monad.Trans.Writer.Lazy), but we may want to understand how it might have been implemented. The data type for the Writer monad could look like this:
-- Computations as pairs of value and "output"
newtype Writer w a = Writer { runWriter :: (a, w) }
Thus, a stateful computation is basically a function a value with some output. The output type is assumed to be monoid because an empty output and the combination of outputs is uniformly defined in this manner.
The corresponding instance of the type class Monad follows:
-- Monad instance for Writer
instance Monoid w => Monad (Writer w)
where
return a = Writer (a, mempty)
(Writer (a, w)) >>= f =
let (Writer (b, w')) = f a in
(Writer (b, w `mappend` w'))
The definition of return conveys that a pure computation produces the empty output. The definition of bind conveys that outputs are to be combined (in a certain order) from the operands of bind. Finally, we need to define the writer-specific operation tell for producing ouput:
-- Produce output
tell :: w -> Writer w ()
tell w = Writer ((), w)
In modern Haskell, we also need to make Writer an instance of Applicative (for applicative functors and Functor (for functors). This code is omitted here, but see GitHub for this page.
See Contribution:haskellWriter for a contribution which uses the writer monad.
Ralf Lämmel
edited this article at
Sun, 21 Jun 2020 13:48:31 +0200
User contributions
User edits
Syntax for editing wiki
For you are available next options:will make text bold.
will make text italic.
will make text underlined.
will make text striked.
will allow you to paste code headline into the page.
will allow you to link into the page.
will allow you to paste code with syntax highlight into the page. You will need to define used programming language.
will allow you to paste image into the page.
is list with bullets.
is list with numbers.
will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.
will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.
will allow your to insert code snippets from @worker.
Syntax for editing wiki
For you are available next options:will make text bold.
will make text italic.
will make text underlined.
will make text striked.
will allow you to paste code headline into the page.
will allow you to link into the page.
will allow you to paste code with syntax highlight into the page. You will need to define used programming language.
will allow you to paste image into the page.
is list with bullets.
is list with numbers.
will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.
will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.
will allow your to insert code snippets from @worker.