#haskell help request
I can't figure out why and how the following works to give a "powerset" of a list
---
filterM (\x -> [True, False]) [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
---
similarly I'm comparing map and mapM and trying to understand why the difference
map (\x -> [True, False]) [1,2]
[[True,False],[True,False]]
mapM (\x -> [True, False]) [1,2]
[[True,True],[True,False],[False,True],[False,False]]
ghci>
@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).
this is the "nondeterminism" some textbooks use?
thanks for the explanation and I think I understand what you're saying
however my brain wants to understand in concrete terms what's really going on
perhaps I should explore an simpler example with x = [1,2]
@rzeta0 In concrete terms, you have to look at the definition of filterM, which is apparently:
Tariq
Oriel Jutty 
filterM p = foldr (\ x -> liftA2 (\ flg -> if flg then (x:) else id) (p x)) (pure [])
It is defined in terms of liftA2 and pure, which for lists are defined as:
pure x = [x]
liftA2 f xs ys = [f x y | x <- xs, y <- ys]
Also, for didactic reasons, let's restore the second parameter of the function passed to liftA2:
(\flg -> if flg then (x:) else id)
-- eta
(\flg rest -> if flg then x : rest else rest)
... and the one passed to foldr, too:
(\ x -> liftA2 (...) (p x))
-- eta
(\x z -> liftA2 (...) (p x) z)
Putting it all together gives
pure x = [x]
liftA2 f xs ys = [f x y | x <- xs, y <- ys]
filterM p = foldr (\x z -> liftA2 (\flg rest -> if flg then x : rest else rest) (p x) z) (pure [])
and after inlining (and renaming the conflicting variables to x' and y')
filterM p = foldr (\x z -> [(\flg rest -> if flg then x : rest else rest) x' y' | x' <- p x, y' <- z]) [[]]
and then
filterM p = foldr (\x z -> [(if x' then x : y' else y') | x' <- p x, y' <- z]) [[]]
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.
thank you for putting in the effort to explain this
this is really good !
I will print it out tomorrow to study it over a coffee line by line
but 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
if that is correct, albeit simple, then I am happy about where the combinations come from
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
@rzeta0 The "action" of the list monad is "There are multiple possible solutions, so try all of them." So for example, if you
do
x <- [1,2]
y <- [3,4]
return (x+y)
you will get 4 solutions which are essentially equivalent to list comprehension [x+y | x <- [1,2], y <- [3,4]]. The evaluation of `x <- [1,2]` first assumes x=1, generates all solutions with that x, and then assumes x=2 and again generates all solution. The final result is all solutions concatenated.
is there an "unfolder" which allows me to see what the do notation translates into
I think looking at a nested set of >>= might help me understand **why** this works
(I am told the list comprehension also uses this mechanism internally)
(foo <- bar; …) in do-notation always translates to ( bar >>= (\foo -> …)) without do-notation, because that's exactly what the do-notation is syntactic sugar for.
Thus @exa's example translates to
[1,2] >>= (\x ->
[3,4] >>= (\y ->
[x + y]
)
)
I doubt that is of much help.🤷
Now, it AFAIK also translates to the list comprehension
[x + y | x <- [1, 2], y <- [3, 4]]
which might be more enlightening, if you already know how list comprehensions with multiple generators behave.
you're right - the translation into >>= doesn't explain how multiple values are processed to create all the combinations
thanks for trying to help though!
I'm looking at the outer bit
[1,2] >>= (\x -> ...
and so x takes on each value of [1,2]
is that the core mechanism which creates all them combinations ?
I think it is .. but I'm uncertain as I'm still learning this
@rzeta0 yup, the definition of >>= for lists says literally "run the function on the right for all values from the list on the left, and concatenate all results".
This definition should be equivalent to what's in the library:
xs >>= f =
concat (map f xs)
@rzeta0 the previous example would be
[1,2] >>= \x ->
[3,4] >>= \y ->
[x+y]
...the lambda with \x is "called" 2 times.
Btw., a slightly easier way to look at it is by observing examples with the "side effects":
(+) <$> Just 1 <*> Just 3
(+) <$> Nothing <*> Just 3
(+) <$> Right 1 <*> Right 3
(+) <$> Right 1 <*> Left "3 is missing!"
(+) <$> readLn <*> readLn
(+) <$> id <*> (+2) $ 1
(+) <$> [1] <*> [3]
(+) <$> [1,2] <*> [3]
(+) <$> [1,2] <*> [3,4]
@rzeta0 To the Hoogle!
https://hoogle.haskell.org/?hoogle=filterm&scope=set%3Ahaskell-platform
Unfortunately, filterM's documentation https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:filterM is useless, unless one already has good intuition for how Haskellers generalize stuff towards Applicatives or Monads:
> This generalizes the list-based filter function.
[slow clap] (That much we can guess from the type signature and name. Yay.)
The implementation https://hackage.haskell.org/package/ghc-internal-9.1201.0/docs/src/GHC.Internal.Control.Monad.html#filterM also isn't all that enlightening at first sight.
So let's do a web search:
https://duckduckgo.com/?q=haskell+filterM
@rzeta0 Interestingly, the first search result is exactly your question: https://stackoverflow.com/questions/28872396/understanding-filterm
Answers seem to be from back when filterM actually worked on Monads rather than also on Applicatives, but as Monads are just special Applicatives, I guess they all still apply (if they were correct to start with).
Also promising looks the second search result https://blog.ssanj.net/posts/2018-04-10-how-does-filterm-work-in-haskell.html. I haven't read it yet, but it looks very thorough.
mirek kratochvil
das-g