Headline

A monad for synthesizing results or output

Illustration

Let us put to work the writer monad in a simple 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

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. 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.

We can also use do notation:

-- Monadic style interpreter
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)

The data type for the state monad looks 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 the 101repo.

See Contribution:haskellWriter for a contribution which uses the writer monad.

Metadata



There are no revisions for this page.

User contributions

    This user never has never made submissions.

    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.

    10 most similar pages:

    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.