Haskell – 123 – altre monadi ancora – 4

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 )
Ok, modules loaded: Main.
*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.

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d blogger hanno fatto clic su Mi Piace per questo: