tb-wtg
Last Updated: February 25, 2016
·
1.566K # Nondeterminism in Haskell with concatMap

###### nondeterminism

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

``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 `concatMap`s 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 `concatMap`s.

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.