Proposal for adding flatten to itertools

Ideas
1

Abstract

I am proposing the addition of a flatten function to the itertools module. While Python provides various ways to flatten iterables (list comprehensions, recursion, or third-party libraries), there is currently no performant, “batteries-included” way to handle nested iterables that is consistent with the standard library’s design philosophy.

Motivation

Flattening nested structures is a common task in data processing, configuration parsing, and general scripting. The current standard approaches have trade-offs:

  • List comprehensions: Only work for 1-level nesting and are not lazy.
  • Recursion: Can be prone to stack overflow and is non-trivial to implement correctly for beginners.
  • Third-party dependencies: Relying on more-itertools is not always possible in restricted or minimal environments. A standardized itertools.flatten would provide a memory-efficient, lazy, and robust implementation that follows itertools design patterns.

Proposed Implementation

from collections.abc import Iterable

def flatten(iterable):
    """Yield items from an iterable, recursively flattening nested iterables."""
    for item in iterable:
        if isinstance(item, Iterable) and not isinstance(item, (str, bytes)):
            yield from flatten(item)
        else:
            yield item

Key Considerations

  • Lazy Evaluation: Like other itertools functions, this would be an iterator, ensuring it remains memory-efficient for large or deep datasets.
  • Edge Cases: The implementation explicitly handles strings and bytes to prevent infinite recursion, an issue often encountered by those writing their own custom flatten functions.
  • API Design: I am proposing this for itertools rather than a method on the list class to avoid modifying the built-in type’s API surface while providing a high-performance, standard tool.
3 Likes
2

Looks like this is available in more-itertools: collapse. So you just want to promote it?

2 Likes
3

Not really relevant to the discussion at hand, but note that the PEP 798 generator expression semantics will make (*iterable for iterable in nested_iterable) a lazy (albeit single-level) flattening expression.

1 Like
4

The implementation for this function is here. Notably, it uses an explicit stack instead of recursion. If this is added, seems worth considering.

2 Likes
5

When people talk about flattering, there are two questions: is it 1-level or recursive? And what should be flattened? The common pitfal is str, which is an iterable producing 1-character strings, which also are iterables. You specialcased them in your example, as well as bytes. What about bytearrays, are they so different from bytes objects? What about dicts, are you fine with flattening their keys and losing values? What about other kinds of array, matrices, etc? What about open files?

Answers on that questions are always application-specific, this is why every application that needs flattering has it’s own implementation (or several).

13 Likes
6

You can define extra base_types that are not flattened. Add an optional flattenable_type that when defined restricts flattenable types to only those contained therein. That would allow, for example, lists to be flattened but other types treated as base.

7

The function needs to guard for recursive iterables, i.e. an iterable containing itself:

a = [1, 2, 3]
a.append(a)
a.append(4)
a  # prints [1, 2, 3, […], 4] with […] indicating recursion
a[3] is a  # prints True

As is, flatten recurses until the stack is full:

flatten(a)  # raises RecursionError
8

collapsing recursive iterables just yields infinite iterables. There’s no need to guard against it.

import more_itertools

a = [1,2,3]
a.append(a)
a.append(4)

for _, i in zip(range(10), more_itertools.collapse(a)):
  print(i)

prints 1,2,3,1,2,3,1,2,3,1. Perfectly good and well-defined behaviour.

Of course list(more_itertools.collapse(a)) is an error, but so is list(count())

1 Like
9

What would you expect with this instead?

a = [1,2,3]
a.insert(0, a)
2 Likes
10

I see the value in more-itertools. collapse, but I believe having a basic, highly-optimized version in the standard itertools would be beneficial for users who cannot or do not want to pull in external dependencies for such a fundamental task

1 Like
11

I appreciate you outlining why a ‘general purpose’ flatten is problematic for the standard library—specifically the ambiguity around dictionaries, bytearrays, and I/O streams. And it sounds like the primary objection is that any ‘universal’ flatten would have to make too many assumptions. But If I were to refine this proposal to be more ‘opinionated’ and strictly target nested iterables of containers (like lists/tuples) while explicitly ignoring maps, files, and other complex objects, does that reduce the ambiguity enough to be considered, or is the consensus that this remains strictly an ‘application-specific’ concern that should never live in the standard library?

12

For this I think there needs to be some evidence. Despite task being simple, it doesn’t mean it is common. I have my own version of this, but it lives among many others which are not in stdlib and in fact I don’t use it as much as I thought I will when I was writing it. Most of the time it is simple list of iterables and chain.from_iterable(iterable) does the trick leaving collapse one of the least used functions.

Now more_itertools is full of many brilliant recipes. Furthermore, documentation of itertools provides some more great recipes, which are not implemented in optimized C code.

If you could provide some analysis of use cases that justify collapse being at the top of the list among fairly big list of other potential additions to itertools, it might be a conversation starter for a more serious discussion.

And note that if there is evidence for that, some bulletproof reasoning for design would need to follow, given that there is a fairly big scope of how to implement it. Now you say:

Yes, it does reduce ambiguity of proposal, but why is this the best version? Maybe the best option would be to resolve ambiguity instead of cutting inconvenient parts off?

2 Likes
13

This seems like it’s very much the case to me as well.

Most examples I can recall of “flattening” are really about taking one data structure (with a particular form) and converting it to another structure (one that is in some sense “flatter”…) In particular, most cases for me are making a list-of-lists into a single-level list, which is precisely what chain.from_iterable handles. But although other cases (probably) exist, I think they are better served by application-specific restructuring functions, and not by a generic function in the stdlib that would always either be a compromise or be so customisable that it’s unusable.

If we find that some other flattening pattern is clearly popular enough to deserve stdlib support, then we could add it in the same way that chain.from_iterable supports the “remove one level of nesting” pattern. But we’d need evidence, not just general assertions like “this is a common task”.

4 Likes
14

Btw your Proposed Implementation is slow, O(n^2) for the whole iteration where n is the number of objects. Real implementation should be O(n).

2 Likes
15

This has been my experience. Every time I have gone down the path of making a flattening function applicable to multiple use cases the bulk of the function ends up being handling those use cases and I have ended up splitting it out into multiple simple special purpose functions. It is much easier to manage 5 functions with names specific to the use cases than try to figure out which args to pass to a do-it-all function to achieve the desired use case.

In light of the fact that there are a huge number of use cases that require flattening, the bloat it would cause to the standard library, and the relative simplicity of each of them, I don’t think it makes sense to include them in the standard library.

2 Likes
16

Right, I think that promoting functions from more-itertools makes sense when the functions are very popular. I think that’s what you need to really show. Of all the functions there, is that the one that most deserves promotion?

In support of your idea, I don’t buy some of the rejection in this thread. The ideas group tends to overcomplicate what I think are relatively simple questions. In this case, the more-itertools people, which include Raymond Hettinger, have already done most of the reasoning about API specification, utility, and what fits with Python. I don’t think it’s worth going back to square one and questioning whether more-itertools got it right.

But if you want to promote collapse, I think you have to show that it deserves promotion.

(Personally, in decades of using Python, I’ve maybe only once or twice needed collapse, but I have needed what is now expressed as (*x for x in y).)

3 Likes
17

Since “flattening” is such an ambiguous concept as many in this thread have pointed out, would it not be better to treat it as a sort of serialization problem (like how json handles default and cls for fallback decoding).

I do feel like at that point you’d be abandoning the speed problem to solve the more abstract problem of a general flattener though.

Since there are already existing fast solutions to flattening simple iterables, maybe a better proposal would be a general way of “flattening” arbitrary collections of data structures?

18

I was just reading the more-itertools docs, collapse is pretty slick.

19

How many projects have you done that needed this functionality?

I like batteries included, but I for don’t want a big pile of odd battery sizes to sift through when all I need is a AAA battery for the remote.

1 Like
20

Add me to the list of “realized itertools.chain.from_iterable() was all the flatten I needed”.

In fact, in the one place I needed it, I was flattening a list of lists of tuples, so a more aggressive flatten() would’ve done the wrong thing. Or I would’ve had to add additional code to rein it in so it didn’t splat my endpoint pairs.

So, yeah… while I sympathize with the “Why isn’t this in itertools???” reaction, I also get why it’s not in itertools. There’s More Than One Way To Do It is that other language.

1 Like