I was experimenting with haskell classes, and I discovered that (at least some) Traversable data structures are also Applicative
And when you look at the definition of Traversable, you see that it can be defined with the sequenceA function:
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
And since list is both Traversable and Applicative, I did try to use sequenceA on a list of lists:
-- this thing ...
sequenceA [[0, 1], [7, 8, 9]]
-- is evaluated as [[0,7],[0,8],[0,9],[1,7],[1,8],[1,9]]
And I get the cartesian product of the 2 lists!
And it even works for a bigger number of lists.
What is it the case?
What is the intuition behind the behaviour of this function?
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!