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:

  1. 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).
  2. 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:

let x = f a
    y = g b
    in h x y

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:

  1. 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.
  2. 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:
h <$> (f a) <*> (g c)

Or use monadic syntax:

do x <- f a
   y <- g b
   return h x y

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.