How do I implement a list comprehension using map and filter?

Question

Both map and filter can be implemented using list comprehension:

map f xs    = [f x | x <- xs]
filter p xs = [x | x <- xs, p x] 

I'd like to show that the converse holds as well using the following example:

[expr | p <- s]

I've got so far:

map (\p -> expr) s

But this works only when pattern matching with p succeeds on all elements of s. In a way, I first want to filter s using a pattern matching on p. Naturally, I tried looking into this question but I haven't been able to find a solution which didn't use list comprehension or LambdaCase.

Answer 1

But this works only when pattern matching with p succeeds on all elements of s.

Indeed: the pattern matching behaviour you describe cannot, in general, be achieved with map and filter alone. Expressing comprehensions in such terms only works well in the simpler case of comprehensions with a single generator and patterns that won't fail. Rather, list comprehensions are specified in the Haskell Report in terms of concatMap. In particular, the clause about generators covers the possibility of pattern match failure:

--This is pseudo-Haskell; see the Report for the fine print.
[  e | p <- l,  Q ] = let ok p = [  e | Q ]
                          ok _ = []
                          in concatMap ok l

The handling of match failures corresponds to what fail does in the desugaring of list monad do-blocks.

Answer 2

Yes, you cannot do pattern matching on a lambda without either using \x -> case x of... (or LambdaCase to shorten it); your example:

[2*x | (x,2) <- [(1,2), (3,4)]]

would have to be implemented as:

map (\(x,_) -> 2*x) $ filter (\(_,y) -> y == 2) [(1,2), (3,4)]

Or, using LambdaCase:

map (\(x,_) -> 2*x) $ filter (\case (_,2) -> True; _ -> False) [(1,2), (3,4)]

Also, for a point-free version:

map ((2*) . fst) $ filter ((==2) . snd) [(1,2), (3,4)]