(This answer assumes traverse
instead of mapM
, but the two functions are largely equivalent. mapM
exists mainly for historical reasons.)
Haskell lists can be seen from two different points of view. On one hand, they are a data structure that contains values. On the other hand, they represent a nondeterminism effect. Nondeterminism not in the sense of generating random values, but in the sense of having multiple possible alternatives for a value.
Now, imagine we have two "nondeterministic Int
s" (namely, two lists of Int
s). What if we want to sum them? What does it mean to sum two nondeterministic Int
s?
The answer is provided by the Applicative
instance of []
, in particular the liftA2
function that lets us promote a function that combines Int
s to a function that combines nondeterministic Int
s. Giving it a more concrete signature than it really has:
liftA2 :: (Int -> Int -> Int) -> [Int] -> [Int] -> [Int]
But what does it do? Basically it applies the function to all possible combinations:
ghci> liftA2 (+) [1,2] [5,7]
[6,8,7,9]
There's also a liftA3
that does the same for a ternary function and three nondeterministic values.
Now, what if we had a whole container of regular values, and mapped it with a function that returned nondeterministic values? We would need to combine the produced values for all elements in the container, not just two or three like the liftAX
functions do. There's a different function called traverse
which does the job. It only works for some containers, those that have a Traversable
instance.
And here's a possible source of confusion. In your example, lists are working both as effects (instances of Applicative
) and as containers which can be mapped with an effectful function (instances of Traversable
).
To make it less confusing, let us create our own traversable container different from []
:
data Triad a = Triad a a a deriving (Show,Functor,Foldable,Traversable)
And invoke traverse
like in the example:
traverse (const "abcd") (Triad 1 2 3)
What do we get? Something like:
[Triad 'a' 'a' 'a',Triad 'a' 'a' 'b',Triad 'a' 'a' 'c',...
Which could be seen either as a list of Triad
s, or as a non-deterministic Triad
resulting from combining the nondeterminism effects of const "abcd" 1
, const "abcd" 2
and const "abcd" 3
using the Applicative
instance of []
.
Note: because Triad
always has three components, this would be equivalent to liftA3 Triad (const "abcd" 1) (const "abcd" 2) (const "abcd" 3)
using liftA3
.
It's also equivalent to sequenceA (Triad (const "abcd" 1) (const "abcd" 2) (const "abcd" 3))
using sequenceA
. sequenceA
works with containers whose elements already are "nodetermimistic values".