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
.