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?
[f(x, y) for x in xs for y in ys]
[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?
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.
For loops are faster than list comprehensions to run functions.
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).
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.
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
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With