There's a lot of confusion about what the various kinds of things you can iterate over in Python. I'll attempt to collect definitions for all of the relevant terms, and provide examples, here, so I don't have to go over the same discussions in the same circles every time.

Some previous posts that may be relevant here:


iteration

Iteration is what a for loop does (whether a for statement, a comprehension, or the C-API equivalent). It's also, of course, what functions like map, zip, list, and islice do under the covers.

The thing you iterate (loop) over is an iterable.

The way you iterate over it (usually implicitly, with a for loop) is to call the iter function, which gives you an iterator. You then call next on the iterator until it raises StopIteration. This is called the iteration protocol

Iterators are always iterables—if you call iter with an iterator, you just get the same iterator back. The reverse is, of course, not true.

I'm cheating a bit here, because the iteration protocol is actually defined in terms of the dunder methods __iter__ and __next__ (or the slots tp_iter and tp_next, for C extension types) rather than the functions iter and next, and includes a fallback for iterating over old-style sequence-like things that don't define iterability but do define subscripting with contiguous indices starting from 0. But that rarely comes up nowadays—and the iter function wraps up that fallback. So, you can unread this paragraph.

abstract base class (ABC)

Abstract base classes complement duck-typing by providing a way to define interfaces when other techniques likehasattr() would be clumsy or subtly wrong (for example with magic methods). ABCs introduce virtual subclasses, which are classes that don’t inherit from a class but are still recognized by isinstance() and issubclass(); see the abcmodule documentation. Python comes with many built-in ABCs for data structures (in the collections.abc module), numbers (in the numbers module), streams (in the io module), import finders and loaders (in the importlib.abcmodule). You can create your own ABCs with the abc module.
Many of the types described below have an ABC, in the collections.abc module, that defines the type in terms that can be tested from within the language. For example, every iterable should be a subtype of collections.abc.Iterable.

This isn't always perfect (for example, a type that responds to the iter function, but doesn't return an iterator, isn't really a valid iterable, even if it's a collections.abc.Iterable subtype as far as issubclass is concerned). That's usually not a problem unless someone is deliberately obfuscating their code—except in one case. Many third-party collection types do not subtype the relevant ABCs. For example, a third-party sequence may not be a subtype of collections.abc.Sequence, even though it supports all of the right methods with the right semantics. So, in a discussion, is someone shows "issubclass(Spam, Sequence) == True", that can be taken as proof that Spam is a sequence (unless you have reason to believe that it's intentionally or accidentally being misleading—as was the case for range in Python 3.1…), but "issubclass(Spam, Sequence) == False" doesn't prove that Spam isn't a sequence.

iterable

An object capable of returning its members one at a time. Examples of iterables include all sequence types (such asliststr, and tuple) and some non-sequence types like dictfile objects, and objects of any classes you define with an __iter__() or __getitem__() method. Iterables can be used in a for loop and in many other places where a sequence is needed (zip()map(), ...). When an iterable object is passed as an argument to the built-in functioniter(), it returns an iterator for the object. This iterator is good for one pass over the set of values. When using iterables, it is usually not necessary to call iter() or deal with iterator objects yourself. The for statement does that automatically for you, creating a temporary unnamed variable to hold the iterator for the duration of the loop. See alsoiteratorsequence, and generator.
Fundamentally, an iterable is something that you can use in a for loop. Everything else described here is an iterable. Functions like map, filter, zip, enumerate, etc. can all take any iterable.

iterator

An object representing a stream of data. Repeated calls to the iterator’s __next__() method (or passing it to the built-in function next()) return successive items in the stream. When no more data are available a StopIteration exception is raised instead. At this point, the iterator object is exhausted and any further calls to its __next__() method just raiseStopIteration again. Iterators are required to have an __iter__() method that returns the iterator object itself so every iterator is also iterable and may be used in most places where other iterables are accepted. One notable exception is code which attempts multiple iteration passes. A container object (such as a list) produces a fresh new iterator each time you pass it to the iter() function or use it in a for loop. Attempting this with an iterator will just return the same exhausted iterator object used in the previous iteration pass, making it appear like an empty container.
More information can be found in Iterator Types.
Iterator is a subtype of iterable—that is, every iterator is an iterable. But other things are iterables too, like sequences. What distinguishes an iterator is that calling iter with an iterator returns the iterator itself. This means that iterators are inherently one-shot: once you iterate an iterator, you've got an empty iterator.

There is no concrete type "iterator". Files are iterators. So are the results of generator functions. Many built-in iterable types (like list, range, and set) have their own custom iterator types. They all support the Iterator ABC, but they're not related in any other way.

Iterators are generally lazy—that is, they only produce elements one at a time, on demand. This isn't inherent to the type, it's just that there's very little good reason to ever create a non-lazy iterator; you'd just be wasting time and memory for no benefit.

generator iterator

An object created by a generator function.
Each yield temporarily suspends processing, remembering the location execution state (including local variables and pending try-statements). When the generator iterator resumes, it picks-up where it left-off (in contrast to functions which start fresh on every invocation).
A generator function is a function with a "yield" or "yield from" expression in it. When you call it, what you get back is a generator iterator. You also get generator iterators from generator expressions.

A generator iterator is, as the name implies, an iterator. Generator iterators also support other methods like send, which aren't relevant here.

Generator iterators are obviously inherently lazy—although there's nothing stopping you from writing "yield from f.readlines()", which would in practice be non-lazy.

The word "generator" on its own is ambiguous. According to the glossary and the reference docs for generators, it should refer to generator functions. However, the in-language name "generator", the ABC "collections.abc.Generator", and the function "inspect.isgenerator" all refer to generator iterators (and "inspect.isgeneratorfunction" refers to generator functions). If it isn't clear from the context which one you're talking about, don't use the word on its own.

sequence

An iterable which supports efficient element access using integer indices via the __getitem__() special method and defines a __len__() method that returns the length of the sequence. Some built-in sequence types are liststr,tuple, and bytes. Note that dict also supports __getitem__() and __len__(), but is considered a mapping rather than a sequence because the lookups use arbitrary immutable keys rather than integers.
The collections.abc.Sequence abstract base class defines a much richer interface that goes beyond just__getitem__() and __len__(), adding count()index()__contains__(), and __reversed__(). Types that implement this expanded interface can be registered explicitly using register().
A sequence—something like list, str, or range—is an iterable, but it's not an iterator. In particular, it's always a reusable iterable—you can loop over a list as many times as you want and get the whole list each time.

Many sequences are non-lazy, like list, but some are lazy, like range.

Sometimes, the word "sequence" is confusingly used to mean any reusable non-iterator iterable, or even any non-iterator iterable, rather than specifically a sequence.

Sometimes you'll see the term "almost-sequence", to refer to something which supports indexing, but doesn't support the entire sequence protocol. Before Python 3.2, range as such a type. Even in 3.5, the term is still relevant—an almost-sequence is what you need to get the "fallback" iteration behavior. NumPy arrays are almost-sequences in this sense.

non-iterator iterable

There is no official term for something that's an iterable but not an iterator (which may be why the term "sequence" is sometimes confusingly used for it).

But this is a useful concept to have. It's any type that you can call iter on it, that doesn't return itself. Sequences like list, mappings like dict, views like dict_values, and many other types are all non-iterator iterables.

Most non-iterator iterables are reusable, but there's nothing in the protocol that guarantees this. Sometimes the two concepts are confusingly conflated.

reusable iterable

There is no official term for something that's an iterable, but not an iterator, which can iterate over the same items repeatedly (and, usually, in parallel).

But this is a useful concept to have. Sequences like list, mappings like dict, mapping views like dict_values, and many other types are reusable iterables.

As mentioned above, sometimes this concept is conflated with the previous one, and sometimes the word "sequence" is confusingly used for both of them.

view

The objects returned from dict.keys()dict.values(), and dict.items() are called dictionary views. They are lazy sequences that will see changes in the underlying dictionary. To force the dictionary view to become a full list uselist(dictview). See Dictionary view objects.
In addition to the specific meaning from the glossary, the word "view" is also used for any non-iterator iterable that similarly provides a view of (possibly some of) the (possibly transformed) elements of some other object.

For example, if you have some object that supports the buffer protocol, you can create a memoryview object referencing all or part of its buffer. This is, as the name implies, a view into that other object. If you slice a memoryview, you get another view into the same object.

Similarly, when you slice a NumPy array, what you get back is another NumPy array, which shares the same storage, but accesses it differently.

Note that not all views are sequences. (In fact, dictionary view objects are not, despite what the glossary says. This is an example of the word "sequence" being used loosely for "non-iterator iterable".)

lazy

A lazy iterable creates its elements on demand. For example, range(1, 1000, 3) doesn't create 333 element up-front and store them all in memory; instead, whenever you try to access one (by indexing, by iteration, or otherwise), it calculates it on the fly.

Generally, iterators are lazy, as are views, but something can be lazy without being either—like range.

An iterable that creates each element the first time it's needed, but caches them, is usually still considered lazy. (In fact, this is how lists work in languages built around laziness. But notice that most such languages use "cons lists", which give you a very natural way to release part of the list without releasing the whole thing—so, e.g., you can zip a list and its tail, iterate the result, and it only keeps two elements in memory at the same time. That isn't as easy to do in Python.)

virtual

The word "virtual" in this context isn't defined anywhere, but it's used in other definitions. For example, older versions of the documentation defined range as a "virtual sequence". (I'm not sure the term still appears anywhere in the documentation as of 3.5, but it's still sometimes used in discussions.)

The intended distinction seems to be that a lazy iterable that's not a view onto an actual iterable, but instead computes its values directly.

Looked at another way: a range object is actually providing a view into something—an infinite iterable consisting of all of the integers—but that something doesn't actually exist anywhere in memory—hence "virtual".

container

The term "container" isn't defined anywhere, although there is a corresponding ABC.

The ABC defines non-iterator iterables that support the "in" operator.

However, the term is often used more loosely, as a term for non-iterator iterables in general, or a vague term meaning "sequences, almost-sequences, mappings, sets, views, and other similar things". There aren't too many non-iterator iterables that aren't "similar things", or that don't support "in" testing, so usually there's no confusion here.

collection

The term "collection" isn't defined anywhere. It's often used as a vague synonym for iterable, or an even-vaguer synonym for container.
8

View comments

  1. Nice article! I wonder if my question on SO made you write this. How to subscribe your blog? Where's the rss link?

    ReplyDelete
    Replies
    1. First, I'm just using the default blogger.com settings for everything. I never noticed that they don't expose these links anywhere. (They do have their own "follow" thing, but I'm not sure what it does…) According to their help), you can get an RSS feed at http://stupidpythonideas.blogspot.com/feeds/posts/default?alt=rss (see the help link for other options). I'll see if I can add this in the banner or something; thanks for pointing it out.

      Meanwhile, although related questions do come up all the time on StackOverflow, this post was actually inspired by a discussion on python-ideas. First, two different very experienced Python developers mixed up iterator and iterable. This led into a discussion on what to call non-iterator iterables; whether it's reasonable or degenerate for a non-iterator iterable to return self, not be repeatable, etc.; what the word "virtual" in the docs means; whether "collection" already has a specific meaning or can be used here; etc.

      Most of the answers are in the docs, but not all in one place. I thought gathering them together and organizing them might help others see everything clearly. (Even if it didn't do that, the effort helped me clarify a few things in my head.)

      Delete
    2. I've added the RSS link in the banner. Again, thanks for bringing that up.

      Delete
  2. I wish len would support all the iterables, not just sequences...

    ReplyDelete
    Replies
    1. How could it? The whole point of the iteration protocol is that you can iterate things whose extent isn't know yet, and only calculated/read/received over the network/etc. as they're available. If that weren't true, there wouldn't be any reason not to use sequences.

      A pervasive view-based design could offer many of the same benefits as an iteration-based design, while still allowing you to calculate the length, random-access, reverse-access, etc. whenever possible. But there are problems with that. So far, Swift is the best example I've seen of an attempt among mainstream languages; it's worth looking at if you're interested. (Also see my earlier post on whether Python could adopt Swift-style views—although I have new thoughts on that which I haven't written up yet.)

      Delete
    2. By consuming all the items - that's what all other functions that work on iterables do. And of course, if I use len() on an iterable that is not reusable I must realize very clearly that length is the only thing I'll ever know about this iterable. Now, there are some cases when that is precisely what I want, for example to know how many items in a sequence satisfy a condition (so I'd want to use len() on filter() result or on a comprehension). Currently I have to workaround this limitation using sum(1 for item in it if cond(it)) -- though sum(map(cond, it)) is shorter, it only works for booleans and reads nowhere as clear as len(filter(cond, it))

      Delete
    3. You can write a one-liner function and call it "ilen" (in analogy with imap, ifilter, etc. from 2.x itertools). Or you can install more-itertools and use it from there. Or you can even name it len and shadow the builtin if you really want.

      Even better, you can write "def count(pred, it): return sum(1 for i in it if pred(i))" and then you can just write "count(pred, it)", which is a lot more readable what you want to write (and shorter). In fact, I think that one-liner is also in more-itertools.

      Delete
Hybrid Programming
Hybrid Programming
5
Greenlets vs. explicit coroutines
Greenlets vs. explicit coroutines
6
ABCs: What are they good for?
ABCs: What are they good for?
1
A standard assembly format for Python bytecode
A standard assembly format for Python bytecode
6
Unified call syntax
Unified call syntax
8
Why heapq isn't a type
Why heapq isn't a type
1
Unpacked Bytecode
Unpacked Bytecode
3
Everything is dynamic
Everything is dynamic
1
Wordcode
Wordcode
1
For-each loops should define a new variable
For-each loops should define a new variable
4
Views instead of iterators
Views instead of iterators
2
How lookup _could_ work
How lookup _could_ work
2
How lookup works
How lookup works
7
How functions work
How functions work
2
Why you can't have exact decimal math
Why you can't have exact decimal math
2
Can you customize method resolution order?
Can you customize method resolution order?
1
Prototype inheritance is inheritance
Prototype inheritance is inheritance
1
Pattern matching again
Pattern matching again
The best collections library design?
The best collections library design?
1
Leaks into the Enclosing Scope
Leaks into the Enclosing Scope
2
Iterable Terminology
Iterable Terminology
8
Creating a new sequence type is easy
Creating a new sequence type is easy
2
Going faster with NumPy
Going faster with NumPy
2
Why isn't asyncio too slow?
Why isn't asyncio too slow?
Hacking Python without hacking Python
Hacking Python without hacking Python
1
How to detect a valid integer literal
How to detect a valid integer literal
2
Operator sectioning for Python
Operator sectioning for Python
1
If you don't like exceptions, you don't like Python
If you don't like exceptions, you don't like Python
2
Spam, spam, spam, gouda, spam, and tulips
Spam, spam, spam, gouda, spam, and tulips
And now for something completely stupid…
And now for something completely stupid…
How not to overuse lambda
How not to overuse lambda
1
Why following idioms matters
Why following idioms matters
1
Cloning generators
Cloning generators
5
What belongs in the stdlib?
What belongs in the stdlib?
3
Augmented Assignments (a += b)
Augmented Assignments (a += b)
11
Statements and Expressions
Statements and Expressions
3
An Abbreviated Table of binary64 Values
An Abbreviated Table of binary64 Values
1
IEEE Floats and Python
IEEE Floats and Python
Subtyping and Ducks
Subtyping and Ducks
1
Greenlets, threads, and processes
Greenlets, threads, and processes
6
Why don't you want getters and setters?
Why don't you want getters and setters?
8
The (Updated) Truth About Unicode in Python
The (Updated) Truth About Unicode in Python
1
How do I make a recursive function iterative?
How do I make a recursive function iterative?
1
Sockets and multiprocessing
Sockets and multiprocessing
Micro-optimization and Python
Micro-optimization and Python
3
Why does my 100MB file take 1GB of memory?
Why does my 100MB file take 1GB of memory?
1
How to edit a file in-place
How to edit a file in-place
ADTs for Python
ADTs for Python
5
A pattern-matching case statement for Python
A pattern-matching case statement for Python
2
How strongly typed is Python?
How strongly typed is Python?
How do comprehensions work?
How do comprehensions work?
1
Reverse dictionary lookup and more, on beyond z
Reverse dictionary lookup and more, on beyond z
2
How to handle exceptions
How to handle exceptions
2
Three ways to read files
Three ways to read files
2
Lazy Python lists
Lazy Python lists
2
Lazy cons lists
Lazy cons lists
1
Lazy tuple unpacking
Lazy tuple unpacking
3
Getting atomic writes right
Getting atomic writes right
Suites, scopes, and lifetimes
Suites, scopes, and lifetimes
1
Swift-style map and filter views
Swift-style map and filter views
1
Inline (bytecode) assembly
Inline (bytecode) assembly
Why Python (or any decent language) doesn't need blocks
Why Python (or any decent language) doesn't need blocks
18
SortedContainers
SortedContainers
1
Fixing lambda
Fixing lambda
2
Arguments and parameters, under the covers
Arguments and parameters, under the covers
pip, extension modules, and distro packages
pip, extension modules, and distro packages
Python doesn't have encapsulation?
Python doesn't have encapsulation?
3
Grouping into runs of adjacent values
Grouping into runs of adjacent values
dbm: not just for Unix
dbm: not just for Unix
How to use your self
How to use your self
1
Tkinter validation
Tkinter validation
7
What's the deal with ttk.Frame.__init__(self, parent)
What's the deal with ttk.Frame.__init__(self, parent)
1
Does Python pass by value, or by reference?
Does Python pass by value, or by reference?
9
"if not exists" definitions
"if not exists" definitions
repr + eval = bad idea
repr + eval = bad idea
1
Solving callbacks for Python GUIs
Solving callbacks for Python GUIs
Why your GUI app freezes
Why your GUI app freezes
21
Using python.org binary installations with Xcode 5
Using python.org binary installations with Xcode 5
defaultdict vs. setdefault
defaultdict vs. setdefault
1
Lazy restartable iteration
Lazy restartable iteration
2
Arguments and parameters
Arguments and parameters
3
How grouper works
How grouper works
1
Comprehensions vs. map
Comprehensions vs. map
2
Basic thread pools
Basic thread pools
Sorted collections in the stdlib
Sorted collections in the stdlib
4
Mac environment variables
Mac environment variables
Syntactic takewhile?
Syntactic takewhile?
4
Can you optimize list(genexp)
Can you optimize list(genexp)
MISRA-C and Python
MISRA-C and Python
1
How to split your program in two
How to split your program in two
How methods work
How methods work
3
readlines considered silly
readlines considered silly
6
Comprehensions for dummies
Comprehensions for dummies
Sockets are byte streams, not message streams
Sockets are byte streams, not message streams
9
Why you don't want to dynamically create variables
Why you don't want to dynamically create variables
7
Why eval/exec is bad
Why eval/exec is bad
Iterator Pipelines
Iterator Pipelines
2
Why are non-mutating algorithms simpler to write in Python?
Why are non-mutating algorithms simpler to write in Python?
2
Sticking with Apple's Python 2.7
Sticking with Apple's Python 2.7
Blog Archive
About Me
About Me
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.