Difference between revisions of "Sequence"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
(Created page with "A ''sequence'' is any object or data structure which stores and accesses elements in a ''fixed order''. Built-in sequence types include <code>list</code>, <code>tuple</code>, ...")
 
(copyedit; expand)
Line 1: Line 1:
A ''sequence'' is any object or data structure which stores and accesses elements in a ''fixed order''. Built-in sequence types include <code>list</code>, <code>tuple</code>, <code>string</code>, and <code>range</code>. By contrast, [[Sets | sets]] and [[Dictionaries | dictionaries]], while they share some common features with sequences, are ''not'' themselves sequences. Sequences always support [[Iteration | iteration]] (though not all iterable types are necessarily sequences) and a set of other basic operations.
+
A '''sequence''' is any object or data structure that stores and accesses elements in a ''fixed order''. Built-in sequence types include <code>list</code>, <code>tuple</code>, <code>str</code>, and <code>range</code>. By contrast, [[set]]s and [[dictionary|dictionaries]], while they share some common features with sequences, are ''not'' themselves sequences. Sequences always support [[iteration]] (though not all iterable types are necessarily sequences) and a set of other basic operations.
  
== Sequence Types ==
+
== Types ==
 +
A string (<code>str</code>) is a sequence whose elements are ''characters'' (letters, symbols, or spaces) enclosed in quotation marks.
  
A <code>string</code> is a sequence whose elements are ''characters'' (letters, symbols, or spaces) enclosed in quotation marks.
+
A <code>tuple</code> is a sequence that stores elements of any type. Tuples are constructed by listing elements separated by commas, or by calling <code>tuple(s)</code> for some sequence <code>s</code>.
 
+
A <code>tuple</code> is a sequence which stores elements of any type. Tuples are constructed by listing elements separated by commas, or by calling <code>tuple(s)</code> for some sequence <code>s</code>.
+
  
 
A <code>list</code> also stores elements of any type. Lists behave much like tuples, except lists are mutable (see below). Lists are constructed by enclosing elements in square brackets and separating them by commas, or by calling <code>list(s)</code> for some sequence <code>s</code>.  
 
A <code>list</code> also stores elements of any type. Lists behave much like tuples, except lists are mutable (see below). Lists are constructed by enclosing elements in square brackets and separating them by commas, or by calling <code>list(s)</code> for some sequence <code>s</code>.  
  
== Sequence Operations ==
+
== Operations ==
 
+
=== Length ===
 
The number of elements in a sequence <code>s</code> is given by <code>len(s)</code>.  
 
The number of elements in a sequence <code>s</code> is given by <code>len(s)</code>.  
  
 +
=== Indices and accessing ===
 
Elements in a sequence are organized by ''index'', an integer denoting where that element is located in the ordering. The first element is at index 0, the second and index 1, and so on. This convention is called ''zero-based indexing''. Note that Python also allows ''negative'' indices for convenience. The last element is at -1, the second to last at -2, and so on.
 
Elements in a sequence are organized by ''index'', an integer denoting where that element is located in the ordering. The first element is at index 0, the second and index 1, and so on. This convention is called ''zero-based indexing''. Note that Python also allows ''negative'' indices for convenience. The last element is at -1, the second to last at -2, and so on.
  
A particular element <code>x</code> in a sequence <code>s</code> can be retrieved with <code">s[i]</code>, where <code>i</code> is the index of <code>x</code>. Note that this returns, but does not remove, the element <code>x</code>. Negative indices are permissible.
+
A particular element <code>x</code> in a sequence <code>s</code> can be retrieved with <code>s[i]</code>, where <code>i</code> is the index of <code>x</code>. Note that this returns, but does not remove, the element <code>x</code>. Negative indices are permissible.
 
+
Indices are also used to return a ''slice'' of the sequence. For a sequence <code>s</code>, create a slice with the format <code>s[start:end:step]</code>. This will return a subsequence which begins with the element at index <code>start</code>, ends with the element at index <code>end - 1</code>, counting indices by <code>step</code>. If not specified <code>start</code> defaults to 0, <code>end</code> defaults to <code>len(s)</code>, and <code>step</code> defaults to 1. Negative indices and steps (indicating counting indices backwards) are permissible. For example,
+
  
 +
=== Slicing ===
 +
Indices are also used to return a ''slice'' of the sequence. For a sequence <code>s</code>, create a slice with the format <code>s[start:end:step]</code>. This will return a subsequence that begins with the element at index <code>start</code>, ends with the element at index <code>end - 1</code>, counting indices by <code>step</code>. If not specified <code>start</code> defaults to 0, <code>end</code> defaults to <code>len(s)</code>, and <code>step</code> defaults to 1. Negative indices and steps (indicating counting indices backwards) are permissible. For example,
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 
>>> s = "abababab"
 
>>> s = "abababab"
Line 25: Line 25:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Two sequences of the same type can be ''concatenated'' together with the addition operator, which returns a new sequence containing all the elements in the first sequence followed by all the elements in the second. For example, <code>(1, 2) + (3, 4)</code> returns <code>(1, 2, 3, 4)</code>.  
+
=== Concatenation ===
 +
Two sequences of the same type can be ''concatenated'' together with the addition operator, which returns a new sequence containing all the elements in the first sequence followed by all the elements in the second. For example, <code>(1, 2) + (3, 4)</code> returns <code>(1, 2, 3, 4)</code>.
  
== Mutable Sequences ==
+
=== Membership test ===
 +
For sequence <code>s</code>, <code>x in s</code> returns <code>True</code> if <code>x</code> is an element of <code>s</code>. <code>x not in s</code> returns the inverse: returns <code>True</code> if <code>x</code> is not an element of <code>s</code>. For example:
 +
<syntaxhighlight lang="python">
 +
>>> 1 in [1, 2, 3]
 +
True
 +
>>> 1 not in [1, 2, 3]
 +
False
 +
</syntaxhighlight>
 +
 
 +
For strings, <code>in</code> and <code>not in</code> act like a substring test. For example:
 +
<syntaxhighlight lang="python">
 +
>>> 'abc' in 'abcde'
 +
True
 +
</syntaxhighlight>
 +
 
 +
=== Shallow copy ===
 +
For sequence <code>s</code> and integer <code>n</code>, <code>s * n</code> returns <code>n</code> shallow copies of <code>s</code> concatenated. For example:
 +
<syntaxhighlight lang="python">
 +
>>> 'hi ' * 3
 +
'hi hi hi '
 +
</syntaxhighlight>
  
The only built-in [[Mutable Types | mutable]] sequence type in Python is the <code>list</code>. In addition to the common sequence operations, lists can support internal modification. For example,  
+
== Mutable sequences ==
 +
The only built-in [[mutable types|mutable]] sequence type in Python is the <code>list</code>. In addition to the common sequence operations, lists support internal modification. For example,  
  
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
Line 69: Line 91:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Other built-in methods which rely upon mutability include <code>sort</code> which sorts the given list object ''in-place'' (without having to return a copy), and <code>reverse</code>, which reverses a list object in-place.
+
Other built-in methods that rely upon mutability include <code>sort</code> which sorts the given list object ''in-place'' (modifies the original object), and <code>reverse</code>, which reverses a list object in-place.

Revision as of 15:50, 2 June 2014

A sequence is any object or data structure that stores and accesses elements in a fixed order. Built-in sequence types include list, tuple, str, and range. By contrast, sets and dictionaries, while they share some common features with sequences, are not themselves sequences. Sequences always support iteration (though not all iterable types are necessarily sequences) and a set of other basic operations.

Types

A string (str) is a sequence whose elements are characters (letters, symbols, or spaces) enclosed in quotation marks.

A tuple is a sequence that stores elements of any type. Tuples are constructed by listing elements separated by commas, or by calling tuple(s) for some sequence s.

A list also stores elements of any type. Lists behave much like tuples, except lists are mutable (see below). Lists are constructed by enclosing elements in square brackets and separating them by commas, or by calling list(s) for some sequence s.

Operations

Length

The number of elements in a sequence s is given by len(s).

Indices and accessing

Elements in a sequence are organized by index, an integer denoting where that element is located in the ordering. The first element is at index 0, the second and index 1, and so on. This convention is called zero-based indexing. Note that Python also allows negative indices for convenience. The last element is at -1, the second to last at -2, and so on.

A particular element x in a sequence s can be retrieved with s[i], where i is the index of x. Note that this returns, but does not remove, the element x. Negative indices are permissible.

Slicing

Indices are also used to return a slice of the sequence. For a sequence s, create a slice with the format s[start:end:step]. This will return a subsequence that begins with the element at index start, ends with the element at index end - 1, counting indices by step. If not specified start defaults to 0, end defaults to len(s), and step defaults to 1. Negative indices and steps (indicating counting indices backwards) are permissible. For example,

>>> s = "abababab"
>>> s[:-2:2]
"aaa"

Concatenation

Two sequences of the same type can be concatenated together with the addition operator, which returns a new sequence containing all the elements in the first sequence followed by all the elements in the second. For example, (1, 2) + (3, 4) returns (1, 2, 3, 4).

Membership test

For sequence s, x in s returns True if x is an element of s. x not in s returns the inverse: returns True if x is not an element of s. For example:

>>> 1 in [1, 2, 3]
True
>>> 1 not in [1, 2, 3]
False

For strings, in and not in act like a substring test. For example:

>>> 'abc' in 'abcde'
True

Shallow copy

For sequence s and integer n, s * n returns n shallow copies of s concatenated. For example:

>>> 'hi ' * 3
'hi hi hi '

Mutable sequences

The only built-in mutable sequence type in Python is the list. In addition to the common sequence operations, lists support internal modification. For example,

>>> lst = [1, 2, 3]
>>> lst[0] = 5
>>> lst
[5, 2, 3]

This piece of code creates lst and replaces its first element. As opposed to concatenation and slicing, which leave the original unchanged and create new sequence objects with the specified modification, this changes the original list object itself.

Other operations which change the list object include append, which takes in one argument and inserts that at the end of the list,

>>> lst.append(5)
>>> lst
[5, 2, 3, 5]

remove, which takes in one argument and removes the first instance of it from the list,

>>> lst.remove(5)
>>> lst
[2, 3, 5]

and pop, which removes and returns the last element if it is not passed any additional arguments, or removes the element at index i for integer i

>>> lst.pop()
5
>>> lst
[2, 3]
>>> lst.pop(0)
2
>>> lst
[3]

Other built-in methods that rely upon mutability include sort which sorts the given list object in-place (modifies the original object), and reverse, which reverses a list object in-place.