Does Writer Monad guarantee right associative concatenation?

Question

It was claimed in Validations in Haskell that use of a Writer guarantees right-associative concatenation. However, this example seems to show otherwise. What's the correct answer?

{-# LANGUAGE OverloadedStrings #-}

import Control.Monad.Writer
import Data.String

data TM = TMempty
        | TMappend TM TM
        | TMfromString String

instance IsString TM where
  fromString = TMfromString

instance Monoid TM where
  mempty  = TMempty
  mappend = TMappend

instance Show TM where
  showsPrec d TMempty = showString "\"\""
  showsPrec d (TMfromString s) = showString $ show s
  showsPrec d (TMappend a b) = showParen (d > 0) $
    showsPrec 1 a .
    showString " ++ " .
    showsPrec 0 b

theWriter :: Writer TM ()
theWriter = do
  tell "Hello"
  replicateM_ 2 $ tell "World"
  tell "!"

main = print $ execWriter theWriter

Produces:

"Hello" ++ ("World" ++ "World" ++ "") ++ "!"

Gopherwood

+1 for the simple example of using and implementing showsPrec. – Bradshaw

Interestingly, if you replace replicateM_ with replicateM, the output becomes "Hello" ++ ("World" ++ ("World" ++ "" ++ "") ++ "") ++ "!" – Gopherwood

It's the difference between sequence and sequence_: sequence = foldr (liftM2 (:)) (return []) but sequence_ = foldr (>>) (return ()); the former generates more binds because it does things with the results. – Claycomb

In any case, >> is supposed to be associative. But I am not a monadic lawyer. – Bradshaw

@JoeyAdams: Indeed; if w follows the Monoid laws, Writer w will follow the Monad laws. But non-right-associative mappends are usually inefficient. – Claycomb

Answer 1

Yes, this is indeed untrue. From the source code:

m >>= k  = WriterT $ do
    ~(a, w)  <- runWriterT m
    ~(b, w') <- runWriterT (k a)
    return (b, w `mappend` w')

...

-- | @'tell' w@ is an action that produces the output @w@.
tell :: (Monoid w, Monad m) => w -> WriterT w m ()
tell w = WriterT $ return ((), w)

So the chain of mappends will mirror the chain of (>>=)s.

Claycomb

Answer 2

Writer [a] doesn't guarantee right-associative concatenation, but you can get guaranteed right-associative concatenation with Writer (Endo [a]).

Earthward