Last Updated: February 25, 2016
·
1.931K # 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

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

15.91K
6

9.593K
2

### Setting a lambda prompt in Haskell

8.295K
4

#### Have a fresh tip? Share with Coderwall community! nobbz
15.79K gnclmorais
9.567K owainlewis
8.245K  Abizern
5.192K
Awesome Job

Full Stack Developer - Complex Events Platform
·
London, United Kingdom
·
Full Time