# 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 `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.