Display / reduce equivalent for multiple list comprehension for sentences

Question

I want to write the functional equivalent of lists, using only higher order functions and no side effects. I do this for rigorous training. I know that list comprehension is Pythonic. In Python, map(f, xs) 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 returns only lists of the same length. reduce is more general, you can implement map and filter on 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 is not generalized to> 2 for sentences. And B is even more complicated since the iteration variable from the 1st place sentence is used in the second sentence. How to write a function (or a set of functions) that implement list recognition functions?

Answer 1

This is the monad template, in particular the list monad. In many languages, monads are hidden behind some kind of syntactic sugar, for example C # LINQ , Scala concept sequences , Haskell do-notation, or, in more languages, (multi-) (for example, in Python).

The key term in translating from any of these sugar syntaxes to ordinary functions is (in the particular case of lists) a function of the type ([a], a -> [b]) -> [b] , which is an essential part of the definition of a monad. This function is known by various names, for example. (>>=) or "bind", flatMap or concatMap , or selectMany .

In the case of lists, concatMap or flatMap is probably the best name because this is what it does: map the function that returns the lists above the list by specifying a list of lists; then flatten this list.

---

Now for something more specific ¹ :

 > 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 although the map like function is always required for the monad, as a rule, reduce not enough, but in fact, we need a generalized join “smoothing” operation with a type of type m<m<a>> (using the template / generalization syntax ), where m is the type of monad under consideration.

¹ 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 (>>=) ≡ join . fmap .

Answer 2

You can use itertools.starmap and itertools.product for case A :

 from itertools import product, starmap list(starmap(f, product(xs, ys))) 

Demo:

 >>> from operator import mul >>> [mul(x, y) for x in range(1, 4) for y in 'abc'] ['a', 'b', 'c', 'aa', 'bb', 'cc', 'aaa', 'bbb', 'ccc'] >>> list(starmap(mul, product(range(1, 4), 'abc'))) ['a', 'b', 'c', 'aa', 'bb', 'cc', 'aaa', 'bbb', 'ccc']