CINXE.COM

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <meta name="color-scheme" content="light dark"> <title>PEP 218 – Adding a Built-In Set Object Type | peps.python.org</title> <link rel="shortcut icon" href="../_static/py.png"> <link rel="canonical" href="https://peps.python.org/pep-0218/"> <link rel="stylesheet" href="../_static/style.css" type="text/css"> <link rel="stylesheet" href="../_static/mq.css" type="text/css"> <link rel="stylesheet" href="../_static/pygments.css" type="text/css" media="(prefers-color-scheme: light)" id="pyg-light"> <link rel="stylesheet" href="../_static/pygments_dark.css" type="text/css" media="(prefers-color-scheme: dark)" id="pyg-dark"> <link rel="alternate" type="application/rss+xml" title="Latest PEPs" href="https://peps.python.org/peps.rss"> <meta property="og:title" content='PEP 218 – Adding a Built-In Set Object Type | peps.python.org'> <meta property="og:description" content="This PEP proposes adding a Set module to the standard Python library, and to then make sets a built-in Python type if that module is widely used. After explaining why sets are desirable, and why the common idiom of using dictionaries in their place is ..."> <meta property="og:type" content="website"> <meta property="og:url" content="https://peps.python.org/pep-0218/"> <meta property="og:site_name" content="Python Enhancement Proposals (PEPs)"> <meta property="og:image" content="https://peps.python.org/_static/og-image.png"> <meta property="og:image:alt" content="Python PEPs"> <meta property="og:image:width" content="200"> <meta property="og:image:height" content="200"> <meta name="description" content="This PEP proposes adding a Set module to the standard Python library, and to then make sets a built-in Python type if that module is widely used. After explaining why sets are desirable, and why the common idiom of using dictionaries in their place is ..."> <meta name="theme-color" content="#3776ab"> </head> <body> <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <symbol id="svg-sun-half" viewBox="0 0 24 24" pointer-events="all"> <title>Following system colour scheme</title> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round"> <circle cx="12" cy="12" r="9"></circle> <path d="M12 3v18m0-12l4.65-4.65M12 14.3l7.37-7.37M12 19.6l8.85-8.85"></path> </svg> </symbol> <symbol id="svg-moon" viewBox="0 0 24 24" pointer-events="all"> <title>Selected dark colour scheme</title> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round"> <path stroke="none" d="M0 0h24v24H0z" fill="none"></path> <path d="M12 3c.132 0 .263 0 .393 0a7.5 7.5 0 0 0 7.92 12.446a9 9 0 1 1 -8.313 -12.454z"></path> </svg> </symbol> <symbol id="svg-sun" viewBox="0 0 24 24" pointer-events="all"> <title>Selected light colour scheme</title> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round"> <circle cx="12" cy="12" r="5"></circle> <line x1="12" y1="1" x2="12" y2="3"></line> <line x1="12" y1="21" x2="12" y2="23"></line> <line x1="4.22" y1="4.22" x2="5.64" y2="5.64"></line> <line x1="18.36" y1="18.36" x2="19.78" y2="19.78"></line> <line x1="1" y1="12" x2="3" y2="12"></line> <line x1="21" y1="12" x2="23" y2="12"></line> <line x1="4.22" y1="19.78" x2="5.64" y2="18.36"></line> <line x1="18.36" y1="5.64" x2="19.78" y2="4.22"></line> </svg> </symbol> </svg> <script> document.documentElement.dataset.colour_scheme = localStorage.getItem("colour_scheme") || "auto" </script> <section id="pep-page-section"> <header> <h1>Python Enhancement Proposals</h1> <ul class="breadcrumbs"> <li><a href="https://www.python.org/" title="The Python Programming Language">Python</a> » </li> <li><a href="../pep-0000/">PEP Index</a> » </li> <li>PEP 218</li> </ul> <button id="colour-scheme-cycler" onClick="setColourScheme(nextColourScheme())"> <svg aria-hidden="true" class="colour-scheme-icon-when-auto"><use href="#svg-sun-half"></use></svg> <svg aria-hidden="true" class="colour-scheme-icon-when-dark"><use href="#svg-moon"></use></svg> <svg aria-hidden="true" class="colour-scheme-icon-when-light"><use href="#svg-sun"></use></svg> <span class="visually-hidden">Toggle light / dark / auto colour theme</span> </button> </header> <article> <section id="pep-content"> <h1 class="page-title">PEP 218 – Adding a Built-In Set Object Type</h1> <dl class="rfc2822 field-list simple"> <dt class="field-odd">Author<span class="colon">:</span></dt> <dd class="field-odd">Greg Wilson <gvwilson at ddj.com>, Raymond Hettinger <python at rcn.com></dd> <dt class="field-even">Status<span class="colon">:</span></dt> <dd class="field-even"><abbr title="Accepted and implementation complete, or no longer active">Final</abbr></dd> <dt class="field-odd">Type<span class="colon">:</span></dt> <dd class="field-odd"><abbr title="Normative PEP with a new feature for Python, implementation change for CPython or interoperability standard for the ecosystem">Standards Track</abbr></dd> <dt class="field-even">Created<span class="colon">:</span></dt> <dd class="field-even">31-Jul-2000</dd> <dt class="field-odd">Python-Version<span class="colon">:</span></dt> <dd class="field-odd">2.2</dd> <dt class="field-even">Post-History<span class="colon">:</span></dt> <dd class="field-even"><p></p></dd> </dl> <hr class="docutils" /> <section id="contents"> <details><summary>Table of Contents</summary><ul class="simple"> <li><a class="reference internal" href="#introduction">Introduction</a></li> <li><a class="reference internal" href="#rationale">Rationale</a></li> <li><a class="reference internal" href="#proposal">Proposal</a></li> <li><a class="reference internal" href="#set-notation">Set Notation</a></li> <li><a class="reference internal" href="#history">History</a></li> <li><a class="reference internal" href="#mutability">Mutability</a></li> <li><a class="reference internal" href="#copyright">Copyright</a></li> </ul> </details></section> <section id="introduction"> <h2><a class="toc-backref" href="#introduction" role="doc-backlink">Introduction</a></h2> <p>This PEP proposes adding a Set module to the standard Python library, and to then make sets a built-in Python type if that module is widely used. After explaining why sets are desirable, and why the common idiom of using dictionaries in their place is inadequate, we describe how we intend built-in sets to work, and then how the preliminary Set module will behave. The last section discusses the mutability (or otherwise) of sets and set elements, and the solution which the Set module will implement.</p> </section> <section id="rationale"> <h2><a class="toc-backref" href="#rationale" role="doc-backlink">Rationale</a></h2> <p>Sets are a fundamental mathematical structure, and are very commonly used in algorithm specifications. They are much less frequently used in implementations, even when they are the “right” structure. Programmers frequently use lists instead, even when the ordering information in lists is irrelevant, and by-value lookups are frequent. (Most medium-sized C programs contain a depressing number of start-to-end searches through malloc’d vectors to determine whether particular items are present or not…)</p> <p>Programmers are often told that they can implement sets as dictionaries with “don’t care” values. Items can be added to these “sets” by assigning the “don’t care” value to them; membership can be tested using <code class="docutils literal notranslate"><span class="pre">dict.has_key</span></code>; and items can be deleted using <code class="docutils literal notranslate"><span class="pre">del</span></code>. However, the other main operations on sets (union, intersection, and difference) are not directly supported by this representation, since their meaning is ambiguous for dictionaries containing key/value pairs.</p> </section> <section id="proposal"> <h2><a class="toc-backref" href="#proposal" role="doc-backlink">Proposal</a></h2> <p>The long-term goal of this PEP is to add a built-in set type to Python. This type will be an unordered collection of unique values, just as a dictionary is an unordered collection of key/value pairs.</p> <p>Iteration and comprehension will be implemented in the obvious ways, so that:</p> <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">S</span><span class="p">:</span> </pre></div> </div> <p>will step through the elements of S in arbitrary order, while:</p> <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="nb">set</span><span class="p">(</span><span class="n">x</span><span class="o">**</span><span class="mi">2</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">S</span><span class="p">)</span> </pre></div> </div> <p>will produce a set containing the squares of all elements in S, Membership will be tested using <code class="docutils literal notranslate"><span class="pre">in</span></code> and <code class="docutils literal notranslate"><span class="pre">not</span> <span class="pre">in</span></code>, and basic set operations will be implemented by a mixture of overloaded operators:</p> <table class="docutils align-default"> <tbody> <tr class="row-odd"><td><code class="docutils literal notranslate"><span class="pre">|</span></code></td> <td>union</td> </tr> <tr class="row-even"><td><code class="docutils literal notranslate"><span class="pre">&</span></code></td> <td>intersection</td> </tr> <tr class="row-odd"><td><code class="docutils literal notranslate"><span class="pre">^</span></code></td> <td>symmetric difference</td> </tr> <tr class="row-even"><td><code class="docutils literal notranslate"><span class="pre">-</span></code></td> <td>asymmetric difference</td> </tr> <tr class="row-odd"><td><code class="docutils literal notranslate"><span class="pre">==</span> <span class="pre">!=</span></code></td> <td>equality and inequality tests</td> </tr> <tr class="row-even"><td><code class="docutils literal notranslate"><span class="pre"><</span> <span class="pre"><=</span> <span class="pre">>=</span> <span class="pre">></span></code></td> <td>subset and superset tests</td> </tr> </tbody> </table> <p>and methods:</p> <table class="docutils align-default"> <tbody> <tr class="row-odd"><td><code class="docutils literal notranslate"><span class="pre">S.add(x)</span></code></td> <td>Add “x” to the set.</td> </tr> <tr class="row-even"><td><code class="docutils literal notranslate"><span class="pre">S.update(s)</span></code></td> <td>Add all elements of sequence “s” to the set.</td> </tr> <tr class="row-odd"><td><code class="docutils literal notranslate"><span class="pre">S.remove(x)</span></code></td> <td>Remove “x” from the set. If “x” is not present, this method raises a <code class="docutils literal notranslate"><span class="pre">LookupError</span></code> exception.</td> </tr> <tr class="row-even"><td><code class="docutils literal notranslate"><span class="pre">S.discard(x)</span></code></td> <td>Remove “x” from the set if it is present, or do nothing if it is not.</td> </tr> <tr class="row-odd"><td><code class="docutils literal notranslate"><span class="pre">S.pop()</span></code></td> <td>Remove and return an arbitrary element, raising a <code class="docutils literal notranslate"><span class="pre">LookupError</span></code> if the element is not present.</td> </tr> <tr class="row-even"><td><code class="docutils literal notranslate"><span class="pre">S.clear()</span></code></td> <td>Remove all elements from this set.</td> </tr> <tr class="row-odd"><td><code class="docutils literal notranslate"><span class="pre">S.copy()</span></code></td> <td>Make a new set.</td> </tr> <tr class="row-even"><td><code class="docutils literal notranslate"><span class="pre">s.issuperset()</span></code></td> <td>Check for a superset relationship.</td> </tr> <tr class="row-odd"><td><code class="docutils literal notranslate"><span class="pre">s.issubset()</span></code></td> <td>Check for a subset relationship.</td> </tr> </tbody> </table> <p>and two new built-in conversion functions:</p> <table class="docutils align-default"> <tbody> <tr class="row-odd"><td><code class="docutils literal notranslate"><span class="pre">set(x)</span></code></td> <td>Create a set containing the elements of the collection “x”.</td> </tr> <tr class="row-even"><td><code class="docutils literal notranslate"><span class="pre">frozenset(x)</span></code></td> <td>Create an immutable set containing the elements of the collection “x”.</td> </tr> </tbody> </table> <p>Notes:</p> <ol class="arabic simple"> <li>We propose using the bitwise operators “<code class="docutils literal notranslate"><span class="pre">|&</span></code>” for intersection and union. While “<code class="docutils literal notranslate"><span class="pre">+</span></code>” for union would be intuitive, “<code class="docutils literal notranslate"><span class="pre">*</span></code>” for intersection is not (very few of the people asked guessed what it did correctly).</li> <li>We considered using “<code class="docutils literal notranslate"><span class="pre">+</span></code>” to add elements to a set, rather than “add”. However, Guido van Rossum pointed out that “<code class="docutils literal notranslate"><span class="pre">+</span></code>” is symmetric for other built-in types (although “<code class="docutils literal notranslate"><span class="pre">*</span></code>” is not). Use of “add” will also avoid confusion between that operation and set union.</li> </ol> </section> <section id="set-notation"> <h2><a class="toc-backref" href="#set-notation" role="doc-backlink">Set Notation</a></h2> <p>The PEP originally proposed <code class="docutils literal notranslate"><span class="pre">{1,2,3}</span></code> as the set notation and <code class="docutils literal notranslate"><span class="pre">{-}</span></code> for the empty set. Experience with Python 2.3’s <code class="docutils literal notranslate"><span class="pre">sets.py</span></code> showed that the notation was not necessary. Also, there was some risk of making dictionaries less instantly recognizable.</p> <p>It was also contemplated that the braced notation would support set comprehensions; however, Python 2.4 provided generator expressions which fully met that need and did so it a more general way. (See <a class="pep reference internal" href="../pep-0289/" title="PEP 289 – Generator Expressions">PEP 289</a> for details on generator expressions).</p> <p>So, Guido ruled that there would not be a set syntax; however, the issue could be revisited for Python 3000 (see <a class="pep reference internal" href="../pep-3000/" title="PEP 3000 – Python 3000">PEP 3000</a>).</p> </section> <section id="history"> <h2><a class="toc-backref" href="#history" role="doc-backlink">History</a></h2> <p>To gain experience with sets, a pure python module was introduced in Python 2.3. Based on that implementation, the set and frozenset types were introduced in Python 2.4. The improvements are:</p> <ul class="simple"> <li>Better hash algorithm for frozensets</li> <li>More compact pickle format (storing only an element list instead of a dictionary of key:value pairs where the value is always <code class="docutils literal notranslate"><span class="pre">True</span></code>).</li> <li>Use a <code class="docutils literal notranslate"><span class="pre">__reduce__</span></code> function so that deep copying is automatic.</li> <li>The BaseSet concept was eliminated.</li> <li>The <code class="docutils literal notranslate"><span class="pre">union_update()</span></code> method became just <code class="docutils literal notranslate"><span class="pre">update()</span></code>.</li> <li>Auto-conversion between mutable and immutable sets was dropped.</li> <li>The <code class="docutils literal notranslate"><span class="pre">_repr</span></code> method was dropped (the need is met by the new <code class="docutils literal notranslate"><span class="pre">sorted()</span></code> built-in function).</li> </ul> <p>Tim Peters believes that the class’s constructor should take a single sequence as an argument, and populate the set with that sequence’s elements. His argument is that in most cases, programmers will be creating sets from pre-existing sequences, so that this case should be the common one. However, this would require users to remember an extra set of parentheses when initializing a set with known values:</p> <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">Set</span><span class="p">((</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">))</span> <span class="c1"># case 1</span> </pre></div> </div> <p>On the other hand, feedback from a small number of novice Python users (all of whom were very experienced with other languages) indicates that people will find a “parenthesis-free” syntax more natural:</p> <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">Set</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span> <span class="c1"># case 2</span> </pre></div> </div> <p>Ultimately, we adopted the first strategy in which the initializer takes a single iterable argument.</p> </section> <section id="mutability"> <h2><a class="toc-backref" href="#mutability" role="doc-backlink">Mutability</a></h2> <p>The most difficult question to resolve in this proposal was whether sets ought to be able to contain mutable elements. A dictionary’s keys must be immutable in order to support fast, reliable lookup. While it would be easy to require set elements to be immutable, this would preclude sets of sets (which are widely used in graph algorithms and other applications).</p> <p>Earlier drafts of <a class="pep reference internal" href="../pep-0218/" title="PEP 218 – Adding a Built-In Set Object Type">PEP 218</a> had only a single set type, but the <code class="docutils literal notranslate"><span class="pre">sets.py</span></code> implementation in Python 2.3 has two, Set and ImmutableSet. For Python 2.4, the new built-in types were named <code class="docutils literal notranslate"><span class="pre">set</span></code> and <code class="docutils literal notranslate"><span class="pre">frozenset</span></code> which are slightly less cumbersome.</p> <p>There are two classes implemented in the “sets” module. Instances of the Set class can be modified by the addition or removal of elements, and the ImmutableSet class is “frozen”, with an unchangeable collection of elements. Therefore, an ImmutableSet may be used as a dictionary key or as a set element, but cannot be updated. Both types of set require that their elements are immutable, hashable objects. Parallel comments apply to the “set” and “frozenset” built-in types.</p> </section> <section id="copyright"> <h2><a class="toc-backref" href="#copyright" role="doc-backlink">Copyright</a></h2> <p>This document has been placed in the Public Domain.</p> </section> </section> <hr class="docutils" /> <p>Source: <a class="reference external" href="https://github.com/python/peps/blob/main/peps/pep-0218.rst">https://github.com/python/peps/blob/main/peps/pep-0218.rst</a></p> <p>Last modified: <a class="reference external" href="https://github.com/python/peps/commits/main/peps/pep-0218.rst">2025-02-01 08:55:40 GMT</a></p> </article> <nav id="pep-sidebar"> <h2>Contents</h2> <ul> <li><a class="reference internal" href="#introduction">Introduction</a></li> <li><a class="reference internal" href="#rationale">Rationale</a></li> <li><a class="reference internal" href="#proposal">Proposal</a></li> <li><a class="reference internal" href="#set-notation">Set Notation</a></li> <li><a class="reference internal" href="#history">History</a></li> <li><a class="reference internal" href="#mutability">Mutability</a></li> <li><a class="reference internal" href="#copyright">Copyright</a></li> </ul> <br> <a id="source" href="https://github.com/python/peps/blob/main/peps/pep-0218.rst">Page Source (GitHub)</a> </nav> </section> <script src="../_static/colour_scheme.js"></script> <script src="../_static/wrap_tables.js"></script> <script src="../_static/sticky_banner.js"></script> </body> </html>