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.

This blog post was originally posted at my Blogspot blog at this URL.