Map/reduce equivalent for a list comprehension with multiple for clauses

Question

I want to write a functional equivalent of the list comprehensions using higher-order functions only and without side effects. I do this for strictly learning purposes. I know that list comprehensions are Pythonic. In Python map(f, xs) is equivalent to [f(x) for x in xs]. But what are the equivalents of these below?

• A: [f(x, y) for x in xs for y in ys]
• B: [f(x, y) for x in range(1, 5) for y in range(x, 5)]

map only returns lists of the same length. reduce is more general, you can implement map and filter upon it.

map(f, xs) == reduce(lambda a, e: a + [f(e)], xs, [])
filter(p, xs) == reduce(lambda a, e: a + [e] if p(e) else a, xs, [])

Therefore A can be implemented as:

def map2(f, xs, ys):
    reduce(lambda a, x: a + map(lambda y: f(x, y), ys), xs, [])

But this doesn't generalize to >2 for clauses. And B is even more tricky, as the iteration variable from 1st for clause is used in the 2nd clause. How do i write a function (or set of functions) that implement list comprehension functionality?

Answer 1

This is the pattern of a monad, specifically the list monad. In many languages, monads are hidden behind some kind of syntactic sugar, such as C#'s LINQ, Scala's sequence comprehensions, Haskell's do-notation or, in even more languages, (multi-)list comprehensions (like here in Python).

The key term in translating from any of these sugary syntaxes to ordinary functions is (in the special case of lists) a function of type ([a], a -> [b]) -> [b], which is the essential part of the definition of a monad. This function is known under different names, e.g. (>>=) or "bind", flatMap or concatMap, or selectMany.

For the case of lists, concatMap or flatMap is probably the best name, because that's what it does: map a function, which returns lists, over a list, giving a list of lists; then, flatten that list.

---

Now for something more concrete¹:

> from functools import reduce
> from operator import add
> def concatMap(xs, f):
      return reduce(add, map(f, xs), []) # only map and reduce!

Testing:

> [x*y for x in range(1 ,5) for y in range(x, 5)]
> [1, 2, 3, 4, 4, 6, 8, 9, 12, 16]
> concatMap(range(1, 5), lambda x: concatMap(range(x, 5), lambda y:[x*y]))
> [1, 2, 3, 4, 4, 6, 8, 9, 12, 16]

And more fun:

> [x*y+z for x in range(1, 5) for y in range(x, 5) for z in range(x, y)]
> [3, 4, 5, 5, 6, 7, 8, 10, 11, 15]
> concatMap(range(1, 5),lambda x: concatMap(range(x, 5), lambda y: concatMap(range(x, y),lambda z: [x*y+z])))
> [3, 4, 5, 5, 6, 7, 8, 10, 11, 15]

---

Finally, it should be noted that though a map-like function is always required for a monad, in general reduce is not enough -- what's actually needed is a generalized "flattening" operation join, with a type like m<m<a>>, (using template/generics syntax), where m is the type of the monad in question.

¹As noted in the comments, this can also be defined as concatMap = lambda xs, f: chain.from_iterable(map(f, xs)), using itertools and the identity (>>=) ≡ join . fmap.