What is non-determinism in Haskell?
haskell
Solution
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
Problem
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.