Why does the list functor represent a context of nondeterministic choice?

Question

What does this quote mean?

the list functor represents a context of nondeterministic choice;

In the context of Functors in functional programming.

I think I understand that a Functor is a "container" of some kind along with the ability to apply a function uniformly to elements in the container without altering the structure. So maybe is a Functor that represents a context or container with possible failure, but why does list represent a context or container with nondeterministic choice?

Answer 1

As best as I can tell, a calculation is "nondeterministic" if it has multiple possible answers. Well, a list can contain multiple possible answers. So that's why.

(As to why it's called nondeterministic, I have no idea... I would have expected nondeterministic to mean random, which is something quite different.)

Answer 2

Traditionally, in computability and complexity, a nondeterministic computation model has referred to a model in which case you can "branch". Wikipedia explains it like so:

In computational complexity theory, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations (imagine a man walking down a path in a forest and, every time he steps further, he must pick which fork in the road he wishes to take). These algorithms do not arrive at a solution for every possible computational path; however, they are guaranteed to arrive at a correct solution for some path (i.e., the man walking through the forest may only find his cabin if he picks some combination of "correct" paths). The choices can be interpreted as guesses in a search process.

In the list monad, this is exactly what you're doing. For example, consider this solution to the decision version of the clique problem, in the list monad:

cliques :: Int -> Graph -> [[Node]]
cliques 0 _ = [[]]
cliques minCliqueSize graph = do
  v <- nodes graph
  vs <- cliques (minCliqueSize - 1) (deleteNode v graph)
  mapM_ (\ w -> guard (isAdjacent v w graph)) vs
  return (v:vs)

This is exactly how you'd program e.g. a nondeterministic Turing machine to solve the clique problem.

Answer 3

Consider the following:

foo = do
  x <- [1 .. 10]
  y <- [2, 3, 5, 7]
  return (x * y)

What is foo? Well, it is x * y, except with the nondeterministic choices of x being a number from 1 to 10, and y being either 2, 3, 5, or 7. Therefore, foo is [2, 3, 5, 7, 4, 6, 10, 14, etc... ]