This blog post was originally posted on my blogpost blog at this URL, and was later migrated to this place. There may be some comments at the original URL.

A deterministic computation has a type `A -> B`

. It has input type `A`

, and result type `B`

. Only one result. Hence just `B`

.

If the computation however is non-determinstic, it would have several possible result values. Let us assume it returns all these possible values in a list. The type of the computation then would be `A -> [B]`

.

Now consider the following two scenarios involving deterministic computations:

- You have two functions:
`f :: A -> B`

, and`g :: B -> C`

. You have to apply`f`

followed by`g`

to a value of type`A`

. That is, the function required would be:`(g . f)`

. - You have three functions:
`f :: A -> B`

,`g :: C -> D`

,`h :: B -> D -> E`

. You have two values, one of type`A`

, other of type`C`

. You apply to them`f`

and`g`

respectively. And the two results you get, you pass them to`h`

. i.e.`h (f a) (g c)`

.

Or in a more verbose manner:

The `Applicative`

and `Monad`

instances for list are defined with the the non-deterministic computation view I talked about above. Let us see how they help us retain composability in the non-deterministic versions of the scenarios we just discussed:

- Our functions now will be:
`f :: A -> [B]`

and`g :: B -> [C]`

. We have a value of type`A`

. We need to apply`f`

to it. Then we will have a list of values of type`B`

. We need to apply`g`

to each of those values. Then we will have`[[C]]`

, which we will have to flatten to get`[C]`

.`List`

’s`Monad`

instance already takes care of these steps, and thus the required function can be obtained with a simple composition:`g <=< f`

. - We have three functions as before:
`f :: A -> [B]`

,`g :: C -> [D]`

, and`h :: B -> D -> E`

. We can use`Applicative`

functions here, as shown below:

Or use monadic syntax:

Pretty close to their deterministic counterparts, aren’t they? To learn more about the Applicative and Monad instances of list, you can refer to this and this chapter from LYAH.