@rzeta0

for now my understanding is that the list comprehension is the mechanism for creating all the "combinations" which are then used by liftA2 and the in turn by filterM

This is correct.

In older versions of the standard library, filterM was defined in terms of Monad, not Applicative, so it probably used liftM2, not liftA2. But in the end, that boils down to >>=, which for lists is just flip concatMap, and list comprehensions like [(x, y) | x <- xs, y <- ys] can always be written in terms of concatMap: flip concatMap xs (\x -> flip concatMap ys (\y -> [(x, y)]))

TMTOWTDI, etc

@BoydStephenSmithJr I just had an awful idea:

😦

@rzeta0 In concrete terms, you have to look at the definition of filterM, which is apparently:

It is defined in terms of liftA2 and pure, which for lists are defined as:

Also, for didactic reasons, let's restore the second parameter of the function passed to liftA2:

... and the one passed to foldr, too:

Putting it all together gives

and after inlining (and renaming the conflicting variables to x' and y')

and then

So what's going on here? We're using foldr to transform an input list into an output list (more specifically, into an output list of lists, i.e. [a] -> [[a]]). Our "accumulator", the z parameter of the function, is a list of possible tails generated so far (or tails that will be generated in the future, depending on how you look at it). Initially, the list of possible tails only has one element: the empty list ([[]]).

p x is our predicate p applied to the current element x. In the (\x -> [True, False]) example, x is ignored and p x is always [True, False].

Using this nested list comprehension, we iterate over all possible predicate values (i.e. [True, False] in this case) and all possible list tails z, and then either prepend the current element x to the current tail y' (x : y') or not (y'), i.e. either include x in the output list or not.

@rzeta0 In a very handwavy way, the [] monad represents multiple universes. So if you have x = [1,2,3], you can think of it as a combination of universes, one where x = 1, one where x = 2, and one where x = 3. The monadic operations on [] let you write code that looks like it only deals with single values (runs in a single universe), but it automatically produces a list of all possible results.

In that interpretation, [True, False] is a multiverse of conditions, with one universe where the condition is True and one where it is False. Hence the filter condition (\x -> [True, False]) says to both include and exclude x from the list of results, and since filterM is "monad aware", it then produces a list of all possible universes (i.e. one where all elements are included, one where all elements are excluded, and everything in between).