Nondeterminism in Haskell with concatMap

Say we have two deterministic functions:

f :: b -> c
g :: a -> b

f takes a value of type b and deterministically produces a value of type
c. g takes a value of type a and deterministically produces a value of
type b.

Say we want to make a function h :: a -> c that applies f to the result of
g. Pretty easy, we could write:

h x = f (g x)

Or, even easier, we can use the function composition operator to do the same
thing.

h = f . g

It's easy when f and g are deterministic. What if they were
nondeterministic?

f' :: b -> (some probabilistic cloud of c values)
g' :: a -> (some probabilistic cloud of b values)

Since Haskell is purely functional, we encode the sets of possible values as
lists:

f' :: b -> [c]
g' :: a -> [b]

They're now deterministic functions that model nondeterministic ones.

How to write h'? Its type should now be a -> [c], but f' still takes only
a single b value as argument. We can use the Haskell version of flat_map,
which is called concatMap.

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f as = concat (map f as)

h' x = concatMap f' (g' x)

Or, even tidier, although this one may look really strange if you aren't used to
Haskell.

h' = concatMap f' . g'

Anyway, the punchline is that you can use concatMap to "glue" together
nondeterministic functions. It's like a nondeterministic version of function
application. Since this is sort of like a specialized form of generic
computation, Haskell provides a monad to do it (the list monad), and all that
does is just hide all the concatMaps under the covers.

This fits with the description of a monad as a "programmable semicolon". What if
you could redefine what a statement is? You might want to redefine statements as
implicitly nondeterministic. That's basically what the list monad does:

h' x = do
    y <- g' x;
    z <- f' y;
    return z;

That's the monadic version. The syntax is a little strange if you're not
familiar with it. return in Haskell doesn't mean exactly the same thing as it
does in other languages either. The do syntax basically says you want to do
something in a monad, and the type-inference engine selects the list monad based
on the fact that f and g result in lists. What the monad does, though, is
glue all these statements together with concatMaps.

It can be used to build up really large nondeterministic functions, but written
sort of like they were deterministic, because that's sort of the way you'd want
to think of it.