Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 930
Mirzhan Irkegulov Avatar asked Feb 28 '14 09:02

Mirzhan Irkegulov


People also ask

Is map more efficient than list comprehension?

Map function is faster than list comprehension when the formula is already defined as a function earlier. So, that map function is used without lambda expression.

What is faster than list comprehension?

For loops are faster than list comprehensions to run functions.

What is the relationship between map calls and list comprehensions?

List comprehension is more concise and easier to read as compared to map. List comprehension are used when a list of results is required as map only returns a map object and does not return any list. Map is faster in case of calling an already defined function (as no lambda is required).

Is list comprehension slower than map?

map may be microscopically faster in some cases (when you're NOT making a lambda for the purpose, but using the same function in map and a listcomp). List comprehensions may be faster in other cases and most (not all) pythonistas consider them more direct and clearer.


1 Answers

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 concrete1:

> 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.

1As 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.

like image 75
phipsgabler Avatar answered Oct 05 '22 07:10

phipsgabler