Haskell – 117 – un po’ di monadi – 5

Continuo da qui, copio qui.

Liste e monadi
So far, we’ve seen how Maybe values can be viewed as values with a failure context and how we can incorporate failure handling into our code by using >>= to feed them to functions. In this section, we’re going to take a look at how to use the monadic aspects of lists to bring non-determinism into our code in a clear and readable manner.

We’ve already talked about how lists represent non-deterministic values when they’re used as applicatives. A value like 5 is deterministic. It has only one result and we know exactly what it is. On the other hand, a value like [3,8,9] contains several results, so we can view it as one value that is actually many values at the same time. Using lists as applicative functors showcases this non-determinism nicely:

Prelude> (*)  [1,2,3]  [10,100,1000]
[10,100,1000,20,200,2000,30,300,3000]

All the possible combinations of multiplying elements from the left list with elements from the right list are included in the resulting list. When dealing with non-determinism, there are many choices that we can make, so we just try all of them, and so the result is a non-deterministic value as well, only it has many more results.

This context of non-determinism translates to monads very nicely. Let’s go ahead and see what the Monad instance for lists looks like:

instance Monad [] where
  return x = [x]
  xs >>= f = concat (map f xs)
  fail _ = []

return does the same thing as pure, so we should already be familiar with return for lists. It takes a value and puts it in a minimal default context that still yields that value. In other words, it makes a list that has only that one value as its result. This is useful for when we want to just wrap a normal value into a list so that it can interact with non-deterministic values.

To understand how >>= works for lists, it’s best if we take a look at it in action to gain some intuition first. >>= is about taking a value with a context (a monadic value) and feeding it to a function that takes a normal value and returns one that has context. If that function just produced a normal value instead of one with a context, >>= wouldn’t be so useful because after one use, the context would be lost. Anyway, let’s try feeding a non-deterministic value to a function:

Prelude> [3,4,5] >>= \x -> [x,-x]
[3,-3,4,-4,5,-5]

When we used >>= with Maybe, the monadic value was fed into the function while taking care of possible failures. Here, it takes care of non-determinism for us. [3,4,5] is a non-deterministic value and we feed it into a function that returns a non-deterministic value as well. The result is also non-deterministic, and it features all the possible results of taking elements from the list [3,4,5] and passing them to the function \x -> [x,-x]. This function takes a number and produces two results: one negated and one that’s unchanged. So when we use >>= to feed this list to the function, every number is negated and also kept unchanged. The x from the lambda takes on every value from the list that’s fed to it.

To see how this is achieved, we can just follow the implementation. First, we start off with the list [3,4,5]. Then, we map the lambda over it and the result is the following: [[3,-3],[4,-4],[5,-5]].

The lambda is applied to every element and we get a list of lists. Finally, we just flatten the list and voila! We’ve applied a non-deterministic function to a non-deterministic value!

Non-determinism also includes support for failure. The empty list [] is pretty much the equivalent of Nothing, because it signifies the absence of a result. That’s why failing is just defined as the empty list. The error message gets thrown away. Let’s play around with lists that fail:

Prelude> [] >>= \x -> ["bad","mad","rad"]
[]
Prelude> [1,2,3] >>= \x -> []
[]

In the first line, an empty list is fed into the lambda. Because the list has no elements, none of them can be passed to the function and so the result is an empty list. This is similar to feeding Nothing to a function. In the second line, each element gets passed to the function, but the element is ignored and the function just returns an empty list. Because the function fails for every element that goes in it, the result is a failure.

Just like with Maybe values, we can chain several lists with >>=, propagating the non-determinism:

Prelude> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

The list [1,2] gets bound to n and ['a','b'] gets bound to ch. Then, we do return (n,ch) (or [(n,ch)]), which means taking a pair of (n,ch) and putting it in a default minimal context. In this case, it’s making the smallest possible list that still presents (n,ch) as the result and features as little non-determinism as possible. Its effect on the context is minimal. What we’re saying here is this: for every element in [1,2], go over every element in ['a','b'] and produce a tuple of one element from each list.

Generally speaking, because return takes a value and wraps it in a minimal context, it doesn’t have any extra effect (like failing in Maybe or resulting in more non-determinism for lists) but it does present something as its result.

When you have non-deterministic values interacting, you can view their computation as a tree where every possible result in a list represents a separate branch.

Here’s the previous expression rewritten in do notation:

ltu.hs

listOfTuples :: [(Int,Char)]
listOfTuples = do
  n <- [1,2]
  ch <- ['a','b']
  return (n,ch)
Prelude> :l ltu
[1 of 1] Compiling Main             ( ltu.hs, interpreted )
Ok, modules loaded: Main.
*Main> listOfTuples
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

This makes it a bit more obvious that n takes on every value from [1,2] and ch takes on every value from ['a','b']. Just like with Maybe, we’re extracting the elements from the monadic values and treating them like normal values and >>= takes care of the context for us. The context in this case is non-determinism.

Using lists with do notation really reminds me of something we’ve seen before. Check out the following piece of code:

*Main> [ (n,ch) | n <- [1,2], ch <- ['a','b'] ]
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

Yes! List comprehensions! In our do notation example, n became every result from [1,2] and for every such result, ch was assigned a result from ['a','b'] and then the final line put (n,ch) into a default context (a singleton list) to present it as the result without introducing any additional non-determinism. In this list comprehension, the same thing happened, only we didn’t have to write return at the end to present (n,ch) as the result because the output part of a list comprehension did that for us.

In fact, list comprehensions are just syntactic sugar for using lists as monads. In the end, list comprehensions and lists in do notation translate to using >>= to do computations that feature non-determinism.

List comprehensions allow us to filter our output. For instance, we can filter a list of numbers to search only for that numbers whose digits contain a 7:

*Main> [ x | x <- [1..50], '7' `elem` show x ]
[7,17,27,37,47]

We apply show to x to turn our number into a string and then we check if the character '7' is part of that string. Pretty clever. To see how filtering in list comprehensions translates to the list monad, we have to check out the guard function and the MonadPlus type class. The MonadPlus type class is for monads that can also act as monoids. Here’s its definition:

class Monad m => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a

mzero is synonymous to mempty from the Monoid type class and mplus corresponds to mappend. Because lists are monoids as well as monads, they can be made an instance of this type class:

instance MonadPlus [] where
  mzero = []
  mplus = (++)

For lists mzero represents a non-deterministic computation that has no results at all — a failed computation. mplus joins two non-deterministic values into one. The guard function is defined like this:

gu.hs

class Monad m => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a

instance MonadPlus [] where
  mzero = []
  mplus = (++)

guard :: (MonadPlus m) => Bool -> m ()
guard True = return ()
guard False = mzero
guard :: (MonadPlus m) => Bool -> m ()
guard True = return ()
guard False = mzero

It takes a boolean value and if it’s True, takes a () and puts it in a minimal default context that still succeeds. Otherwise, it makes a failed monadic value. Here it is in action:

ghci> guard (5 > 2) :: Maybe ()
Just ()
ghci> guard (1 > 2) :: Maybe ()
Nothing
ghci> guard (5 > 2) :: [()]
[()]
ghci> guard (1 > 2) :: [()]
[]

Per qualche motivo che non ho capito non riesco a riprodurre i risultati precedenti.

Looks interesting, but how is it useful? In the list monad, we use it to filter out non-deterministic computations. Observe:

*Main> :l gu
[1 of 1] Compiling Main             ( gu.hs, interpreted )
Ok, modules loaded: Main.
*Main> [1..50] >>= (\x -> guard ('7' `elem` show x) >> return x)
[7,17,27,37,47]

The result here is the same as the result of our previous list comprehension. How does guard achieve this? Let’s first see how guard functions in conjunction with >>:

*Main> guard (5 > 2) >> return "cool" :: [String]
["cool"]
*Main> guard (1 > 2) >> return "cool" :: [String]
[]

If guard succeeds, the result contained within it is an empty tuple. So then, we use >&gt; to ignore that empty tuple and present something else as the result. However, if guard fails, then so will the return later on, because feeding an empty list to a function with >>= always results in an empty list. A guard basically says: if this boolean is False then produce a failure right here, otherwise make a successful value that has a dummy result of () inside it. All this does is to allow the computation to continue.

Here’s the previous example rewritten in do notation:

sevensOnly :: [Int]
sevensOnly = do
  x <- [1..50]
  guard ('7' `elem` show x)
  return x

Ovviamente devo caricare la definizione di guard.

*Main> :l sevensOnly
[1 of 1] Compiling Main             ( sevensOnly.hs, interpreted )
Ok, modules loaded: Main.
*Main> sevensOnly
[7,17,27,37,47]

Had we forgotten to present x as the final result by using return, the resulting list would just be a list of empty tuples. Here’s this again in the form of a list comprehension:

*Main> [ x | x <- [1..50], '7' `elem` show x ]
[7,17,27,37,47]

So filtering in list comprehensions is the same as using guard.

Seguire Miran alle volte –proprio come oggi 👽

😐

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 di 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...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

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