Learn You a Haskell for Great Good! - Miran Lipovaca [130]
In Chapter 11, we talked about how lists represent nondeterministic 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 nondeterminism nicely.
ghci> (*) <$> [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 nondeterminism, there are many choices that we can make, so we just try all of them. This means the result is a nondeterministic value as well, but it has many more results.
This context of nondeterminism translates to monads very nicely. Here’s what the Monad instance for lists looks like:
instance Monad [] where
return x = [x]
xs >>= f = concat (map f xs)
fail _ = []
As you know, return does the same thing as pure, and you’re already familiar with return for lists. return takes a value and puts it in a minimal default context that still yields that value. In other words, return makes a list that has only that one value as its result. This is useful when we want to just wrap a normal value into a list so that it can interact with nondeterministic values.
>>= 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—after one use, the context would be lost.
Let’s try feeding a nondeterministic value to a function:
ghci> [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 nondeterministic value, and we feed it into a function that returns a nondeterministic value as well. The result is also nondeterministic, 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 with the list [3,4,5]. Then we map the lambda over it and get the following result:
[[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 voilà, we’ve applied a nondeterministic function to a nondeterministic value!
Nondeterminism 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:
ghci> [] >>= \x -> ["bad","mad","rad"]
[]
ghci> [1,2,3] >>= \x -> []
[]
In the first line, an empty list is fed into the lambda. Because the list has no elements, there are none to be passed to the function, so the result is an empty list. This is similar to feeding Nothing to a function. In the second line, each element is 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 as with Maybe values, we can chain several lists with >>=, propagating the nondeterminism:
ghci> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n, ch)