• Choose a category
• All
• Classic-Fiction

You can add a logging mechanism to pretty much any function. You just replace normal values with Writer values where you want and change normal function application to >>= (or do expressions if it increases readability).

Inefficient List Construction

When using the Writer monad, you need to be careful which monoid to use, because using lists can sometimes turn out to be very slow. Lists use ++ for mappend, and using ++ to add something to the end of a list is slow if that list is really long.

In our gcd' function, the logging is fast because the list appending ends up looking like this:

a ++ (b ++ (c ++ (d ++ (e ++ f))))

A list is a data structure that’s constructed from left to right. This is efficient, because we first fully construct the left part of a list and only then add a longer list on the right. But if we’re not careful, using the Writer monad can produce list appending that looks like this:

((((a ++ b) ++ c) ++ d) ++ e) ++ f

This associates to the left instead of to the right. It’s inefficient because every time it wants to add the right part to the left part, it must construct the left part all the way from the beginning!

The following function works like gcd', but it logs stuff in reverse. First, it produces the log for the rest of the procedure, and then it adds the current step to the end of the log.

import Control.Monad.Writer

gcdReverse :: Int -> Int -> Writer [String]

Int gcdReverse a b

| b == 0 = do

tell ["Finished with " ++ show a]

return a

| otherwise = do

result <- gcdReverse b (a `mod` b)

tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]

return result

It does the recursion first and binds its resulting value to result. Then it adds the current step to the log, but the current step goes at the end of the log that was produced by the recursion. At the end, it presents the result of the recursion as the final result. Here it is in action:

ghci> mapM_ putStrLn $ snd $ runWriter (gcdReverse 8 3)

Finished with 1

2 mod 1 = 0

3 mod 2 = 1

8 mod 3 = 2

This function is inefficient because it ends up associating the use of ++ to the left instead of to the right.

Because lists can sometimes be inefficient when repeatedly appended in this manner, it’s best to use a data structure that always supports efficient appending. One such data structure is the difference list.

Using Difference Lists

While similar to a normal list, a difference list is actually a function that takes a list and prepends another list to it. For example, the difference list equivalent of a list like [1,2,3] is the function \xs -> [1,2,3] ++ xs. A normal empty list is [], whereas an empty difference list is the function \xs -> [] ++ xs.

Difference lists support efficient appending. When we append two normal lists with ++, the code must walk all the way to the end of the list on the left of ++, and then stick the other one there. But what if we take the difference list approach and represent our lists as functions?

Appending two difference lists can be done like so:

f `append` g = \xs -> f (g xs)

Remember that f and g are functions that take lists and prepend something to them. For instance, if f is the function ("dog"++) (just another way of writing \xs -> "dog" ++ xs) and g is the function ("meat"++), then f `append` g makes a new function that’s equivalent to the following:

\xs -> "dog" ++ ("meat" ++ xs)

We’ve appended two difference lists just by making a new function that first applies one difference list to some list and then to the other.

Let’s make a newtype wrapper for difference lists so that we can easily give them monoid instances:

newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }

The type that we wrap is [a] -> [a], because a difference list is just a function that takes a list and returns another list. Converting normal lists to difference lists and vice versa is easy:

toDiffList :: [a] -> DiffList a

toDiffList xs = DiffList (xs++)

fromDiffList :: DiffList a -> [a]

fromDiffList (DiffList f) = f []

To