Why does the Writer monad require an appending operation?

Learn
#1

I recently learned about difference lists, and how they can be used for efficient concatenation in Haskell. I learned how they actually work through this article: Demystifying DList

When defunctionalized, it seems like a difference list is a data structure that is made of a tree of normal lists, and when you want to convert one to a normal list, you flatten the tree of lists into a list of sublists (abusing the ($) operator as a cons cell, and the sublists being actually closures that capture the sublists), which are then concatenated.

In one chapter of Learn You A Haskell, the author compares the repeated left-associated concatenation of lists to difference lists when demonstrating the Writer monad.

This is pretty interesting, but it makes me wonder: why does the Writer monad require a type that can be appended associatively (i.e. a Monoid)? When logging, aren’t you only ever going to add one item to the list at a time and only at one end? Why does it do the equivalent of [firstReport, secondReport, ...] ++ [newReport] instead of newReport : [..., secondReport, firstReport]? That is, why do you have to have logs that append Monoids instead of just providing an item to add to the log history? Then, you wouldn’t need something like the difference list to make up for this behavior in the first place. When would you need to join concatenate two arbitrarily long log histories together?

#2

I guess because of the type of >>=, no? Writer is really just a tuple (value, log), so the type of >>= is (modulo wrappers and whatnot).

(>>=) :: (a, w) -> (a -> (b, w) -> (b,w)

notice that while the first and second writer have different types of value, they have the same type of log which need to be fused together.

This same reason would apply even if we define monad with >=> or join. We always end up with two logs of the same type, not one log of type [a] and one of type a.

#3

If it’s just like this because that’s what a monad has to do, then wouldn’t that suggest that logging isn’t best described by a monad? Or, maybe that it’s related to and similar to a monad, but slightly different?

But, I’m not really experienced in Haskell, or even really as a programmer. There may be things I don’t know about or that I’m not thinking of.

#4

A single logging statement may only add one item to a list at a time, but imagine you have a program that calls two functions, foo and bar, both of which do logging. The result should log everything that foo logs, plus everything that bar logs. If the logs take the form of a list, you therefore need to append one list to the other.

In other programming languages, you might imagine passing a logger into both foo and bar (often implicitly). To make this a pure operation for Haskell, you could pass some append-only structure into foo, collect the resulting structure, and pass that into bar. This is equivalent to what ultimately happens when you use a difference list as the accumulating monoid.

1 Like
#5

I see, thanks for the explanation! That makes sense.

I’ve also realized that, since the Writer can have any monoid, not just lists or other things that can be appended, my argument may not apply. For example, you could have a Writer Natural (since natural numbers with addition are a monoid) where you’re just recording the number of times something happened, and addition is constant time. (Of course, you’d probably use a more complex type than an integer, but the type could just be a record of integers, and the monoid/semigroup instance could just do summation as an implementation detail).

1 Like
#6

Exactly. I have some work code which uses Writer (specifically the CPS writer) to accumulate warnings as it processes a list of records:

data Report = Report 
  { warnings1 :: Seq WarningType1
  , warnings2 :: Seq WarningType2
  , ...
  } deriving (Semigroup, Monoid) via (Generically Report)

And then for each type of warning, it’s easy to write tell (mempty { warnings1 = Seq.singleton (someWarning1) }.

2 Likes