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
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
gto 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
grespectively. And the two results you get, you pass them to
h (f a) (g c).
Or in a more verbose manner:
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
fto it. Then we will have a list of values of type
B. We need to apply
gto each of those values. Then we will have
[[C]], which we will have to flatten to get
Monadinstance 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
Applicativefunctions here, as shown below:
Or use monadic syntax: