Flatten a list: Difference between revisions

And, in contexts where it may be desirable to avoid not just recursion, but also:

# mutation of the original list, and

# dependence on error-events for evaluation control,

we can again use the universal '''concat . map''' composition (see the second recursive example above) by embedding it in a fold / reduction, and using it with a pure, but iteratively-implemented, '''until''' function.

( Note that the generic functions in the following example are ''curried'', enabling not only more flexible composition, but also some simplifying reductions – here eliminating the need for two uses of Python's ''lambda'' keyword ):

<lang python>from functools import (reduce)

from itertools import (chain)

def flatten(xs):

return reduce(

lambda a, x: a + until(_all(notList))(

concatMap(list)

)([x]),

xs, []

)

def main():

print(

flatten([1, [[[3]]], [[[4, 5, 6]]]])

)

# GENERIC -------------------------------------------------------

# A generalised wrapper for the built-in `all` function,

# extending its range to non-Boolean lists.

# _all :: (a -> Bool) -> [a] -> Bool

def _all(p):

return lambda xs: all(map(p, xs))

# concatMap :: (a -> [b]) -> [a] -> [b]

def concatMap(f):

return lambda xs: list(chain.from_iterable(map(f, xs)))

# notList :: a -> Bool

def notList(x):

return not isinstance(x, list)

# until :: (a -> Bool) -> (a -> a) -> a -> a

def until(p):

def go(f, x):

v = x

while not p(v):

v = f(v)

return v

return lambda f: lambda x: go(f, x)

main()</lang>

{{Out}}

<pre>[1, 3, 4, 5, 6]</pre>