Why is the following Haskell code non-deterministic?

Question

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 computation x + y where x takes on every value from [1,2] and y takes 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?

Answer 1

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