The intuition for the list applicative is that of nondeterministic computation. You can think of a list of type [X]
with n elements as being a calculation that produces an X
, and it's definitely one of the n choices of X
contained in that list, but any of them is possible.
For example, the list ['a','e']
represents a calculation that could produce 'a'
or could produce 'e'
. The list [-4,4]
might be the result of asking about the square root of 16
. The list []
is a nondeterministic calculation that can't correctly produce any value! (Say, the result of asking about the real square root of -16
...)
In this interpretation, when we have a list of functions fs
and some values xs
, the list fs <*> xs
is the list of all the possible results you could get by applying any of the functions in fs
to any of the arguments in xs
. Meanwhile, the list pure x
is the deterministic calculation that always produces exactly one result, namely, x
.
So! If you have a nested list, then there are various alternative ways of thinking about what it means, including that it is a list of nondeterministic calculations or that it is a nondeterministic calculation that produces lists as its result. The sequenceA
function transports you between these representations: it takes a list of nondeterministic calculations and produces a single nondeterministic calculation whose result is a list. So:
[[a,b,c],[d,e],[f,g,h,i]]
You can think of this as a list with three elements. The first is a choice between a
, b
, and c
, the second is a choice between d
and e
, and the third is a choice between f
, g
, h
, and i
. The sequenceA
function will produce a nondeterministic choice of lists, each of which has the same shape as the outer list above; that is, each list we are choosing between will have length 3. The first element will come from [a,b,c]
; the second will come from [d,e]
, and the third from [f,g,h,i]
. If you think for a bit about all the ways that could happen, you will see it's exactly their Cartesian product!