``lib.sequence`` Module
=======================

The sequences defined in this module fall into one of two categories:

* Sequential access (inherited from ``collections.abc.Iterator``)
* Random access (inherited from ``collections.abc.Sequence``)

Sequentially accessible sequences must be computed from their start through to the desired element; they are typically
defined by `recurrence relations <https://en.wikipedia.org/wiki/Recurrence_relation>`_ or where the elements of a
sequence don't have a well-defined ordering. Alternatively, randomly accessible sequences support access to arbitrary
elements from the sequence without having computed all previous elements first.

As per the Python standard library, objects derived from ``collections.abc.Iterator`` implement the iterator protocol,
meaning they represent a stream of data that will be iterated over precisely once. They **do not** support indexing.

Objects derived from ``collections.abc.Sequence`` implement the iterator protocol, however, they also support indexing
and having their length evaluated (via the standard ``len`` function).

.. note:: this module includes some infinite sequences derived from ``collections.abc.Sequence``. While this means the
          standard ``len`` function may be evaluated on them, they will raise a ``TypeError`` as per Python conventions.

For some sequences, there is an efficient membership test to determine whether a given number belongs to that sequence.
These tests can be accessed via Python's ``in`` operator. Those sequences with such functionality will include sample
code illustrating the behaviour; the computational complexity will also be included in a note in the relevant class
documentation.

Observe that many of these sequences are of infinite length, however, applications will only need some finite length
sub-sequence. There are of course many ways to implement this, however, the following example to print all
`Fibonacci numbers <https://en.wikipedia.org/wiki/Fibonacci_number>`_ less than :math:`1000` illustrates a concise
design pattern that can be adopted:

.. code-block:: python

    from itertools import takewhile
    from lib.sequence import Fibonaccis

    for elt in takewhile(lambda f_n: f_n < 1000, Fibonaccis()):
        print(elt)

The ``itertools.takewhile`` function will consume from an iterator while elements satisfy the given predicate (i.e. the
provided function returns ``True`` when evaluated on elements in the given sequence). The first element encountered that
violates the predicate will terminate the iteration.

.. automodule:: lib.sequence
   :members:
   :show-inheritance: