What is non-determinism in Haskell?

Question

What do Haskell programmers mean when they refer to non-determinism? I read that list monads can be used to model non-determinism, but surely lists are not non-deterministic? What does it mean to model non-determinism? As far as I can fathom, this just means returning a set of all possible results for a set of calculations.

Answer 1

Your understanding is correct. Nondeterminism as captured by the list monad indeed deals with computations (functions) that can return multiple possible results.

That is, a computation f that nondeterministically computes outputs of type B from inputs of type A is then in Haskell represented by a function that takes values of type A to lists of values of type B:

f :: A -> [B]

Then, if we also have computation g that—also nondeterministically—computes outputs of type C from inputs of type B,

g :: B -> [C]

we can compose these computations to obtain a combined computation h that takes inputs of type A to outputs of type C:

h :: A -> [C]

In Haskell, defining such a function h involves applying the function g to every possible result of the application f x and then flattening the thus obtained list of lists of possible outcomes for h:

h x = concat zs where zs = [g y | y <- f x]

It is this kind of composition that is captured by the list monad, allowing you to write:

h x = f x >>= g

or even

h = f >=> g