Skip to content

Latest commit

 

History

History
235 lines (181 loc) · 8.81 KB

sequence.md

File metadata and controls

235 lines (181 loc) · 8.81 KB

Python Sequences Types and Interfaces

Sequences support the iterator protocol.

Common Sequence Operations

These divide into three parts. The built-in operations on multiple sequences can take only sequences of the same base type, e.g., list and list, but not tuple and list.

  • Built-in operators: single-type, immutable
  • Built-in operators: single-type, mutation
  • itertools: generic and multi-type operations

Immutable Sequences

See Language Summary for caveats on immutable collections.

Operators, lowest to highest precedence:

  • x [not] in s: Containment or subsequence test.
  • =, <, etc.: Lexicographic by comparing corresponding elements.
  • s + t: Concatenation. Immutable returns new obj. Not supported by some types, e.g., range.
  • s * n, n * s: s + s ... n times using shallow copies. n < 0 is same as n = 0.
  • s[i]: 0-based index. -1 is last item in list.
  • s[i:j]: Slice from i (default 0) up to (but not including) j (default len).
  • s[i:j:k]: Slice with stride k (i, i+k, i+2k, etc.). Negative k strides backwards.
  • len(s)
  • min(s), max(s): smallest/largest item in s.
  • s.index(x, i, j): Index of first occurence of x in s between i (default 0) and j (default len). (No rindex?)
  • s.count(x): Count of occurrences of x in s.
  • hash(): Immutable sequences only. All values must be immutable or TypeError is thrown. Hashable objects that compare equal must have same hash value. More at Hashes and Equality.

When implementing these, collections.abc.Sequence is useful.

See also Using Iterables for more generic methods that operate on iterables, including map, enumerate, zip, filter, max, min, sum, sorted, all, any.

Mutable Sequences

Below, s is any mutable sequence, t is any iterable and x is an object that can be stored in s.

Operators:

  • s[i] = x: Replacement at index.
  • s[i:j] = t: Remove slice, insert contents of iterable.
  • del s[i:j]: Remove slice.
  • s[i:j:k] = t: Replacement at indices. t must have same length.
  • del s[i:j:k]: Remove elements.
  • s *= n: Update s with its contents repeated n times. n <= 0 clears. n is integer or implements __index()__.
  • s.append(x): Append element x to sequence.
  • s.extend(t), s += t: Append all elements of t.
  • s.insert(i, x): Insert x at index i, shifting subsequent elements. (Same as s[i:i] = [x].)
  • s.pop(i): Remove and return element at index i (default -1).
  • s.remove(x): Remove first element == x or raise ValueError.
  • s.clear(), s.copy(): (≥3.3) Remove all elements (del s[:]) and shallow copy (s[:]). For compatibility with non-sequence containers.
  • s.reverse(): In-place reversal returning None. Use reversed(s) to return a reversed iterator (as s[::-1], but also works on non-indexable collections if they support __reversed__())

When implementing these, collections.abc.MutableSequence is useful.

The default values in a slice xs[::] are 0:-1:1. Thus, you can use x[:] to refer to the whole list:

del xs[:]           # Clear (empty) list
xs[:] = [1,2,3]     # Replace contents of list
ys = xs[:]          # Shallow copy (`ys is xs` ⇒ False)

Itertools

itertools offers additional operations that can work on multiple sequences of different types. These are inspired by APL, Haskell and SML.

Infinite:

  • count(start, [step])
  • cycle(xs): repeat each element of p: 'AB' → 'ABABAB...'
  • repeat(x, [n]): Repeat el forever or n times

Terminating on shortest input:

  • accumulate(xs, [f])
  • chain(xs, ...)
  • chain.from_iterable(xs, ...)
  • compress
  • dropwhile
  • filterfalse
  • groupby
  • islice
  • starmap
  • takewhile
  • tee
  • zip_longest

Combinatoric:

  • product
  • permutations
  • combinations
  • combinations_with_replacement

Sequence Types

The built-in sequence types are tuple, list, range, str and bytes.

See also Emulating container types.

tuple

Construct a tuple with tuple() or comma (parens are optional).

()   ;  tuple()     # empty
a,   ;  (a,)        # singleton
a,b  ;  (a,b)       # pair, etc.
tuple(iter)         # from iterable (tuple returns unchanged)

Becuase tuples are immutable, + is inefficient. Extend a list instead.

namedtuple

collections.namedtuple extends standard tuples with access via attribute names. These are exactly as efficient as regular tuples. The typename (first) parameter is used only to set the class' __name__. The classes generated with this can be used directly by assigning them to names or it may also be convenient to use them as superclasses.

from collections import namedtuple as ntup
T0 = ntup('T0', 'foo bar baz'); t0 = T0('a', 'b', 'c')

class T1(ntup('T1', 'a b')):
    def __init__(self, *_): self.sum = self.a + self.b
    def product(self):      return self.a * self.b
    # inherited __str__, __repr__ display ntup name

Constructing ntups with a single **dict parameter can be convenient.

Utility methods/attrs start with _ to avoid collisions:

  • _make(iterable): (Class method) Construct this namedtuple from any iterable.
  • _asdict(): Returns OrderedDict of names→values (dict in Python <3.1).
  • _replace(**kwargs): New tuple with some values replaced.
  • _fields: Tuple of strings listing field names.
  • _fields_defaults: Dictionary mapping field names to default values (≥3.7)

Python ≥3.7 has a defaults kwarg to supply default vaules for init params. For older versions, set default values with:

T3 = ntup('T3', 'a b c')
T3.__new__.__defaults__ = (12,13)   # or e.g.: (None,) * len(T3._fields)
T3(1,2)     # ⇒ T3(1,2,13)
T3(1)       # ⇒ T3(1,12,13)

Subclasses of named tuples may want to set __slots__ to an empty tuple to avoid instance dictionary creation:

class Point(ntup('Point', 'x y')):
    __slots__ == ()
    @property
    def hypot(self):
        return (self.x ** 2 + self.y ** 2) ** 0.5

To build a new class that "extends" an old one, just add fields:

Point3D = ntup('Point3', Point._fields + ('z',))

list

Construct a list with list() or []:

[]; list()          # empty
[a, b, c]           # elements
[x for x in iter]   # comprehension
list(iter)          # from iterable (list arg is shallow copied)

Additional method:

  • sort(*, key=None, reverse=False): Stable in-place sort using <, returning None.

range

A range is a constant size object with containment functions fully implemented. Can be empty. Testing commpares as sequences: range(0) == range(2,1,3).

Construct with range():

range(n)            # 0..n
range(m, n)         # m..n
range(m, n, k)      # stride by k; reverse if negative

Additional attributes: start, stop, step.