Editor

Flatten Anything, Lazily

#147 · Iterators and generators · Advanced · 135 XP · about 30 min

Write a generator flatten(items) that yields every value inside a nested structure, from left to right, as if all the brackets were taken away.

  • Lists, tuples and generators are containers: open them and yield what is inside. They can be nested to any depth.
  • Everything else is a value and is yielded as it is. That includes strings ('abc' stays 'abc'), numbers, None and dictionaries.

flatten must be lazy: it only looks as far ahead as it is asked to, so it works with endless generators inside the structure. It must also cope with very deep nesting, deeper than Python lets a function call itself (about 1,000 levels).

Examples

list(flatten([1, [2, [3, 4]], (5,), []]))        # returns [1, 2, 3, 4, 5]
list(flatten(['ab', ['cd', ('e', None)]]))       # returns ['ab', 'cd', 'e', None]
list(flatten([0, (n * n for n in [1, 2, 3])]))   # returns [0, 1, 4, 9]

from itertools import count, islice
list(islice(flatten([[-1], (n for n in count())]), 4))   # returns [-1, 0, 1, 2]

Constraints

  • Up to 100,000 values in total
  • Nesting can be up to 10,000 levels deep

Note

A generator is what a generator function or a generator expression gives you, and isinstance(x, types.GeneratorType) tells you whether x is one.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.