 Continuo da qui, copio qui, scrollare fino a “Adding logging to programs“.

Aggiungere log a programmi
Euclid’s algorithm is an algorithm that takes two numbers and computes their greatest common divisor. That is, the biggest number that still divides both of them. Haskell already features the `gcd` function, which does exactly this, but let’s implement our own and then equip it with logging capabilities. Here’s the normal algorithm:

mcd.hs

``````gcd' :: Int -> Int -> Int
gcd' a b
| b == 0    = a
| otherwise = gcd' b (a `mod` b)``````

The algorithm is very simple. First, it checks if the second number is 0. If it is, then the result is the first number. If it isn’t, then the result is the greatest common divisor of the second number and the remainder of dividing the first number with the second one. For instance, if we want to know what the greatest common divisor of 8 and 3 is, we just follow the algorithm outlined. Because 3 isn’t 0, we have to find the greatest common divisor of 3 and 2 (if we divide 8 by 3, the remainder is 2). Next, we find the greatest common divisor of 3 and 2. 2 still isn’t 0, so now we have have 2 and 1. The second number isn’t 0, so we run the algorithm again for 1 and 0, as dividing 2 by 1 gives us a remainder of 0. And finally, because the second number is now 0, the final result is 1. Let’s see if our code agrees:

``````Prelude> :l mcd
[1 of 1] Compiling Main             ( mcd.hs, interpreted )
*Main> gcd' 8 3
1``````

It does. Very good! Now, we want to equip our result with a context, and the context will be a monoid value that acts as a log. Like before, we’ll use a list of strings as our monoid. So the type of our new gcd’ function should be:

`gcd' :: Int -> Int -> Writer [String] Int`

All that’s left now is to equip our function with log values. Here’s the code:

mcd-1.hs

``````import Control.Monad.Writer

gcd' :: Int -> Int -> Writer [String] Int
gcd' a b
| b == 0 = do
tell ["Finished with " ++ show a]
return a
| otherwise = do
tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
gcd' b (a `mod` b)``````

This function takes two normal `Int` values and returns a `Writer [String] Int`, that is, an `Int` that has a log context. In the case where `b` is 0, instead of just giving a as the result, we use a do expression to put together a `Writer` value as a result. First we use tell to report that we’re finished and then we use return to present a as the result of the do expression. Instead of this do expression, we could have also written this:

`Writer (a, ["Finished with " ++ show a])`

However, I think the `do` expression is easier to read. Next, we have the case when `b` isn’t 0. In this case, we log that we’re using mod to figure out the remainder of dividing `a` and `b`. Then, the second line of the do expression just recursively calls `gcd'`. Remember, `gcd'` now ultimately returns a `Writer` value, so it’s perfectly valid that `gcd' b (a `mod` b)` is a line in a `do` expression.

While it may be kind of useful to trace the execution of this new `gcd'` by hand to see how the logs get appended, I think it’s more insightful to just look at the big picture and view these as values with a context and from that gain insight as to what the final result will be.

Let’s try our new `gcd'` out. Its result is a `Writer [String] Int` value and if we unwrap that from its newtype, we get a tuple. The first part of the tuple is the result. Let’s see if it’s okay:

``````*Main> fst \$ runWriter (gcd' 8 3)
1``````

Good! Now what about the log? Because the log is a list of strings, let’s use `mapM_ putStrLn` to print those strings to the screen:

``````*Main> mapM_ putStrLn \$ snd \$ runWriter (gcd' 8 3)
8 mod 3 = 2
3 mod 2 = 1
2 mod 1 = 0
Finished with 1``````

I think it’s awesome how we were able to change our ordinary algorithm to one that reports what it does as it goes along just by changing normal values to monadic values and letting the implementation of `>>=` for `Writer` take care of the logs for us. We can add a logging mechanism to pretty much any function. We just replace normal values with `Writer` values where we want and change normal function application to `>>=` (or `do` expressions if it increases readability).

Costruzione inefficiente di liste
When using the `Writer` monad, you have to be careful which monoid to use, because using lists can sometimes turn out to be very slow. That’s because 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))))`

Lists are a data structure that’s constructed from left to right, and 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. This is inefficient because every time it wants to add the right part to the left part, it has to construct the left part all the way from the beginning!

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

mcd-2.hs

``````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 result 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. Finally, it presents the result of the recursion as the final result. Here it is in action:

``````*Main> mapM_ putStrLn \$ snd \$ runWriter (gcdReverse 8 3)
Finished with 1
2 mod 1 = 0
3 mod 2 = 1
8 mod 3 = 2``````

It’s inefficient because it ends up associating the use of `++` to the left instead of to the right.

👽

Posta un commento o usa questo indirizzo per il trackback.