Question about the Writer monad as taught in LYAH. (How did the appending to the log take place?)

Question

I'm learning Haskell from the "Learn you a Haskell for Great Good" tutorial and I've got to the part on writer monads. Here's the example that I can't figure out.

import Control.Monad.Writer

logNumber :: Int -> Writer [String] Int  
logNumber x = writer (x, ["Got number: " ++ show x])  

multWithLog :: Writer [String] Int  
multWithLog = do  
   a <- logNumber 3  
   b <- logNumber 5  
   return (a*b) -- shouldn't return (3*5) result in (15,[]) ?

ghci> runWriter $ multWithLog
(15,["Got number: 3","Got number: 5"]) -- how did that happen? 

I am trying understand how the monoidic value w in the Writer w a monad returned by the do block got changed. The tutorial did not go into details on how the mappending took place.

The type declaration for Writer and the instance declaration for Writer as a monad is given by the tutorial as

newtype Writer w a = Writer { runWriter :: (a, w) }  

instance (Monoid w) => Monad (Writer w) where  
    return x = Writer (x, mempty)
    (Writer (x,v)) >>= f = let (Writer (y, v')) = f x in Writer (y, v `mappend` v')  

if return x results in Writer (x, mempty) as per the instance declaration and mempty for monoid [a] is [], shouldn't return (a*b), which amounts to return (3*5), evaluate to (15,[])?

ghci> return (15) :: Writer [String] Int
WriterT (Identity (15,[]))

I gave the above command to ghci and it returns a WriterT type value, the tuple contains an empty list as expected.

multWithLog :: Writer [String] Int
multWithLog = logNumber 3 >>= (\a -> 
              logNumber 5 >>= (\b -> 
              return (a*b)))

I've rewritten the do block using bind operators instead. The above code gave identical result as the original code in the tutorial.

I'm under the impression that >>= only extracted Int 3 from the result of logNumber 3 and gave it to (\a -> logNumber 5 ...etc.), which then did the logNumber function on a different value (5) and so on. How did these operations lead to the [String] part of the Writer monad being altered?

Answer 1

From the code you posted

(Writer (x,v)) >>= f =
   let (Writer (y, v')) = f x in Writer (y, v `mappend` v')

we can see that indeed f is being called only with the x argument. So in logNumber 3 >>= \a -> ... variable a indeed is bound to 3.

However, >>= does something after calling f, namely it combines v with v'. In your example, v is the [String] coming from logNumber 3 which is ["Got number: 3"]. Instead v' comes form evaluating \a -> ... with a=3, and is ["Got number: 5"].

mappend for lists is ++, which concatenates the lists together. Hence we get the final result.

Allow me to be a little sloppy and neglect the Writer wrappers. We get

return (a*b)
= (a*b, [])

logNumber 5 >>= \b -> return (a*b) 
= logNumber 5 >>= \b -> (a*b, [])
= (5, ["Got number: 5"]) >>= \b -> (a*b, [])
= (a*5, ["Got number: 5"] `mappend` [])
= (a*5, ["Got number: 5"])

logNumber 3 >>= \a -> logNumber 5 >>= \b -> return (a*b)
= logNumber 3 >>= \a -> (a*5, ["Got number: 5"])
= (3, ["Got number: 3"]) >>= \a -> (a*5, ["Got number: 5"])
= (3*5, ["Got number: 3"] `mappend` ["Got number: 5"])
= (15, ["Got number: 3", "Got number: 5"])

Intuitively, we can pretend that a value in your writer monad is an effectful computation, which returns a value (like 3) and as a side effect appends a few messages to a list-of-strings. The log of all such messages is invisible inside the monad (we can only append to the log), and will only be made available at the very end, when we will use runWriter to exit from the monadic context.

Answer 2

This ought to explain it:

> runWriter (return 15) :: (Int, [String])
(15,[])                       -- == runWriter $ writer (15, mempty)

> runWriter (logNumber 3)
(3,["Got number: 3"])         -- == runWriter $ writer (3, ["Got number: 3"])

> runWriter (logNumber 5)
(5,["Got number: 5"])         -- == runWriter $ writer (5, ["Got number: 5"])

> runWriter (logNumber 3 >> logNumber 5)
(5,["Got number: 3","Got number: 5"])   -- == ["Got number: 3"] ++ ["Got number: 5"]

> runWriter (logNumber 3 >>         logNumber 5 >>         return 15        )
(15,["Got number: 3","Got number: 5"])  -- == ["Got number: 3"] ++ ["Got number: 5"] ++ []

> runWriter (logNumber 3 >>= (\_ -> logNumber 5 >>= (\_ -> return 15    ) ) )
(15,["Got number: 3","Got number: 5"])

> runWriter (logNumber 3 >>= (\i -> logNumber 5 >>= (\j -> return (i*j) ) ) )
(15,["Got number: 3","Got number: 5"])

And the last line's monadic expression is equivalent to multWithLog's do block.

Noice the nesting of the lambda functions: the lambda function

                                                    (\j -> return (i*j) )

is situated inside the lambda function

                             (\i -> logNumber 5 >>= (\j -> return (i*j) ) )

That's why the i in that return (i*j) refers to the outer lambda function's argument i, received by it from the outermost monadic action expression, logNumber 3.

How? Because according to the definition of >>= as you quote it in your question, we have

   runWriter ( Writer (x,v) >>= f )
=
   runWriter ( let (Writer (y, u)) = f x in Writer (y, v `mappend` u) )
= 
   let (Writer (y, u)) = f x in runWriter ( Writer (y, v `mappend` u) )
= 
   let (Writer (y, u)) = f x in (y, v `mappend` u) 

i.e.

   runWriter ( logNumber 5 >>= (\j -> return j) )
=                              -------- f -----
   runWriter ( writer (5, ["Got number: 5"]) >>= (\j -> writer (j, mempty)) )
=                  --  x  ------- v -------      -------- f ---------------
   let Writer (y, u) = ( (\j -> writer (j, mempty)) 5 ) 
                         -------- f --------------- x
                            in (y, ["Got number: 5"] `mappend` u) 
=                                  ------- v ------- 
   let (y, u) = (5, mempty) in (y, ["Got number: 5"] `mappend` u) 
=
                               (5, ["Got number: 5"] `mappend` mempty) 

The "monoidic values" from each Writer action do not "get changed". Each action contributes its "monoidic value" into the overall "monoidic value" of the combined Writer-type computation of the do block, built from its Writer-type sub-computations by mappending the monoidic values contributed by each sub-computation (the semantics of Writer), found in the snd field of the tuples representing the actions (the implementation of Writer).

Again, this overall value is combined by combining the monoidic value parts of each tuple, namely, their snd fields. The monoidic combination is mappend, which is done behind the scenes for us by the Writer type computations.

And for lists, mappend [a] [b] == [a] ++ [b] == [a,b], while mappend [a,b] [] == [a,b] ++ [] == [a,b].

Your questions, then:

• shouldn't return (a*b) amount to (15,[])?

  it should, and it does, as we saw at the start of the answer.

• Writer vs. WriterT wrappers

  it doesn't matter. Both are isomorphic, because Identity is a no-op. WriterT is part of monad-transformers implementation of Writer monad; the one given in the book is simpler and easier to follow.

• How did these operations lead to the [String] part of the Writer monad being altered?

  not altered, but combined, by the mappend of the specific Monoid used by the specific Writer; as part of the monadic combination i.e. the monadic bind's, >>=, definition; being as Monads generalize function call protocol and Writer Monad's generalization is collecting a Monoid values behind the scenes, so they can be appended in the shadows, in addition to the user functions doing their work in the open:

   do { a <- logNumber 3  
      ; b <- logNumber 5  
      ; return (a*b)
      }
  =    ----- user area ------       ---- hidden area ---
   do {  a       <- writer (3       , ["Got number: 3"]       )
      ;    b     <- writer (5       , ["Got number: 5"]       )  
      ;             writer (
        (a*b)                       , []                      )
      }
  =
   Writer
      ( (3*5)                       , mconcat [..., ..., ...] )
  

Embrace do-notation, it's your friend. It helps us think abstractly.