I've been learning Haskell from Learn You A Haskell and just came across the following statement:
Doing
(+) <$> [1,2] <*> [4,5,6]results in a non-deterministic computationx + ywherextakes on every value from[1,2]andytakes on every value from[4,5,6].
I don't think I understand what is non-deterministic about this. Is it just that the order of the results or the order of computation is not guaranteed to be the same every time?
The book is using a different sense of "non-deterministic computation" than you are.
You're thinking "non-deterministic computation" as in "a program which doesn't fully determine its output". This kind of non-determinism is common when using multiple parallel threads of execution; there are many possible outputs, and which one you get is arbitrarily determined by the precise order in which things happen at runtime.
The paragraph you're quoting from LYAH is talking about viewing lists as a model of "non-deterministic computation", in a sense that is meant by the logic programming paradigm (if you've ever done much programming using the Prolog language, you'd probably be familiar with this). Non-deterministic programs in this sense have multiple (or zero!) outputs because they are specifically programmed to do so, rather than because they do not fully specify what their output should be.
If "non-determinsitic code" is just code that has "zero or more outputs of type t", this sounds a lot like a function returning a list of t. The list Applicative (and Functor and Monad) instances are just the obvious way of saying how to combine such "non-determinstic values" with each other, and with pure functions. For example, the Functor instance says that if you can apply a function to an A to get a B, then you can also map that function to work on a "non-deterministic A" to get a "non-determinstic B" (by applying the unmapped function to every possible value of the "non-deterministic A").
(+) <$> [1,2] <*> [4,5,6] seen this way is an example of "non-deterministic addition". You add a number that could be 1 or 2, to another number that could be 4, 5, or 6; the result could be 5, 6, 7, 6, 7, or 8 (some possibilities are repeated because there's more than one way to generate them).
In this context, what's nondeterministic isn't the computation that Haskell is performing, but instead the computation that is being represented. When viewed as a monad (or applicative functor), lists represent nondeterministic computation: just as a Maybe a is a computation of an a that might have failed, or an IO a is computation of an a that did some I/O, a [a] is a nondeterministic computation of an a. Thus the list [1,2], under this interpretation, represents a computation that nondeterministically returns 1 or 2, and similarly for [4,5,6]. Or again, by way of analogy: computing Nothing in Haskell succeeds, even though that value represents failure; computing [1,2] in Haskell is deterministic (and pretty boring), but that value encodes a form of nondeterminism.
Thus, (+) <$> [1,2] <*> [4,5,6] computes x + y nondeterministically. Again, that's not what's written in the code – that's what the code represents. The code itself deterministically computes the representation of a nondeterministic computation!
The way this works is that <$> and <*> functions lift computations inside an applicative functor, so that snippet says to compute (+) inside the list applicative functor, which means it computes (+) nondeterministically:
[1,2] represents a computation that could return either 1 or 2. Call its result x.[4,5,6] represents a computation that could return any of 4, 5, or 6. Call its result y.x + y – could evaluate to the sum of any of the possible values for x and y.This is what the quote is saying, just in slightly more and different words :-)
In fact, (+) <$> [1,2] <*> [4,5,6] is exactly equivalent to [x + y | x <- [1,2], y <- [4,5,6]], where the "nondeterminism" is instead x and y each iterating over their respective lists. This is all that's meant by nondeterminism, in the end!
As for how you were thinking about understanding this: remember, Haskell code is guaranteed to be deterministic in its results, thanks to Haskell's purely functional nature. The order of computation, however, doesn't affect this, so is left fairly unconstrained, as long as functions don't fail too early (e.g., const () undefined must evaluate to ()). We only get nondeterminism by representing it as an effect; lists are one encoding of this (and IO can be another, for a very different kind of nondeterminism).
In the list monad, I like to think of [1, 2] as representing a set of possible choices: 1 or 2. When we do operations on such a set, we produce a set of possible results. What is “1 or 2” plus 4? Naturally, “5 or 6”. In Haskell, we can phrase that question as (+ 4) <$> [1, 2] and get the expected answer [5, 6].
The list monad represents nondeterminism in that it lets us talk about the whole tree of possible choices, without actually committing to any of those choices. So what is “1 or 2” plus “4, 5, or 6”? Well, that could be:
We can encode the question in Haskell with the list monad (as exhaustive calculation of all the solutions, in order):
do
x <- [1, 2] -- if x is 1 or 2
y <- [4, 5, 6] -- and y is 4, 5, or 6
return (x + y) -- then what are the possible values of x + y?
Or with the list applicative (doing the same):
(+) <$> [1, 2] <*> [4, 5, 6]
And the answer is of course [5, 6, 7, 6, 7, 8].
If it helps, you can also think of the list monad, or list comprehensions, as performing a sort of Cartesian product.
A different way of encoding this is to start an independent concurrent computation for each of the choices, at once, producing the final results without any inherent order.
