How does mapM work with const functions in Haskell?

Question

as I had been looking for ways to optimize a password cracker I had been making, I came across a much shorter implementation of all possible character combinations in a list, which used this function:

mapM (const xs) [1..n]

where xs could be the characters available, and n the length of the desired words. so

mapM (const "abcd") [1..4]

would output a list ["aaaa","aaab","aaac","aaad","aaba","aabb"..] and so on. Only the length matters for the list of th right, I could have written ['f','h','s','e'] or any 4 element list instead.

I can see why the list doesn't matter, it's passed to a const function. I can see that const of a list technically satisfies (a -> m a).

But my question is: why isn't the output simply ["abcd","abcd","abcd","abcd"], or maybe "abcdabcdabcdabcd"? What does a const function do to output all 4 letter variations for the given letters?

Answer 1

You can understand mapM using this intuition:

mapM f [x1, x2, ..., xN]
=
do y1 <- f x1
   y2 <- f x2
   ...
   yN <- f xN
   return [y1, y2, ..., yN]

In your case:

mapM (const "abcd") [1 .. 4]
=
do y1 <- const "abcd" 1
   y2 <- const "abcd" 2
   y3 <- const "abcd" 3
   y4 <- const "abcd" 4
   return [y1, y2, y3, y4]
=
do y1 <- "abcd"
   y2 <- "abcd"
   y3 <- "abcd"
   y4 <- "abcd"
   return [y1, y2, y3, y4]

The latter is equivalent to a list comprehension

[ [y1, y2, y3, y4] | y1<-"abcd", y2<-"abcd", y3<-"abcd", y4<-"abcd"]

which will produce your output.

Answer 2

(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 Ints" (namely, two lists of Ints). What if we want to sum them? What does it mean to sum two nondeterministic Ints?

The answer is provided by the Applicative instance of [], in particular the liftA2 function that lets us promote a function that combines Ints to a function that combines nondeterministic Ints. 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 Triads, 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".