PSequence¶

pyrsistent_extras._psequence.psequence(iterable: Optional[Iterable[T]] = None) → PSequence[T][source]¶

Create a PSequence from the given items

\(O(n)\)

>>> psequence()
psequence([])
>>> psequence([1,2,3,4])
psequence([1, 2, 3, 4])

Parameters: iterable (Optional[Iterable[T]]) –
Return type: PSequence[T]

pyrsistent_extras._psequence.sq(*elements: T) → PSequence[T][source]¶

Shorthand for psequence()

>>> sq(1,2,3,4)
psequence([1, 2, 3, 4])

Parameters: elements (T) –
Return type: PSequence[T]

class pyrsistent_extras._psequence._python.PSequence[source]¶

Persistent sequence

Meant for cases where you need random access and fast merging/splitting.

Tries to follow the same naming conventions as the built in list/deque where feasible.

Do not instantiate directly, instead use the factory functions sq() or psequence() to create an instance.

The PSequence implements the typing.Sequence protocol and is typing.Hashable.

Most operations are a constant factor (around 2x-3x) slower than the equivalent list operation. However, some are asymptotically faster:

inserting or deleting an item at either end is \(O(1)\)

inserting or deleting an item in the middle is \(O(\log{n})\)

slicing a continguous chunk is \(O(\log{n})\)

merging two sequences is \(O(\log{n})\)

repeating a sequence \(k\) times is \(O(\log{k}\log{n})\) and takes \(O(\log{k}\log{n})\) space

The implementation uses 2-3 finger trees annotated with sizes based on Haskell’s Data.Sequence from the package containers, which is described in

Ralf Hinze and Ross Paterson, “Finger trees: a simple general-purpose data structure”, Journal of Functional Programming 16:2 (2006) pp 197-217. http://www.staff.city.ac.uk/~ross/papers/FingerTree.html

The following are examples of some common operations on persistent sequences:

>>> seq1 = psequence([1, 2, 3])
>>> seq1
psequence([1, 2, 3])
>>> seq2 = seq1.append(4)
>>> seq2
psequence([1, 2, 3, 4])
>>> seq3 = seq1 + seq2
>>> seq3
psequence([1, 2, 3, 1, 2, 3, 4])
>>> seq1
psequence([1, 2, 3])
>>> seq3[3]
1
>>> seq3[2:5]
psequence([3, 1, 2])
>>> seq1.set(1, 99)
psequence([1, 99, 3])

__eq__(other) → bool[source]¶

Return self == other

\(O(n)\)

>>> psequence([1,2,3]) == psequence([1,2,3])
True
>>> psequence([1,2,3]) == psequence([2,3,4])
False

Return type: bool

__ge__(other) → bool[source]¶

Return self >= other

\(O(n)\)

>>> psequence([1,2,3]) >= psequence([1,2,3])
True
>>> psequence([1,2,3]) >= psequence([2,3,4])
False
>>> psequence([1,2,3]) >= psequence([0,1,2])
True

Return type: bool

__getitem__(index: int) → T[source]¶

__getitem__(index: slice) → PSequence[T]

Get the element(s) at the specified position(s)

Time complexities for n[i]:

\(O(\log(\min(i,n−i)))\) getting a single item.
\(O(\log(\max(i,m)))\) getting a contiguous slice.
\(O(\log{n}+m)\) getting a non-contiguous slice.

Raises: IndexError – if the index is out of bounds

>>> psequence([1,2,3,4])[2]
3
>>> psequence([1,2,3,4,5])[1:4]
psequence([2, 3, 4])
>>> psequence([1,2,3,4])[5]
Traceback (most recent call last):
...
IndexError: ...

__gt__(other) → bool[source]¶

Return self > other

\(O(n)\)

>>> psequence([1,2,3]) > psequence([1,2,3])
False
>>> psequence([1,2,3]) > psequence([2,3,4])
False
>>> psequence([1,2,3]) > psequence([0,1,2])
True

Return type: bool

__hash__() → int[source]¶

Calculate the hash of the sequence.

\(O(n)\)

>>> x1 = psequence([1,2,3,4])
>>> x2 = psequence([1,2,3,4])
>>> hash(x1) == hash(x2)
True

Return type: int

classmethod __init_subclass__(*args, **kwargs)¶

This method is called when a class is subclassed.

The default implementation does nothing. It may be overridden to extend subclasses.

__iter__() → Iterator[T][source]¶

Create an iterator

\(O(1)\)

Iterating the entire sequence is \(O(n)\).

>>> i = iter(psequence([1,2,3]))
>>> next(i)
1
>>> next(i)
2
>>> next(i)
3
>>> next(i)
Traceback (most recent call last):
...
StopIteration

Return type: Iterator[T]

__le__(other) → bool[source]¶

Return self <= other

\(O(n)\)

>>> psequence([1,2,3]) <= psequence([1,2,3])
True
>>> psequence([1,2,3]) <= psequence([2,3,4])
True
>>> psequence([1,2,3]) <= psequence([0,1,2])
False

Return type: bool

__len__() → int[source]¶

Get the length of the sequence

\(O(1)\)

>>> len(psequence([1,2,3,4]))
4

Return type: int

__lt__(other) → bool[source]¶

Return self < other

\(O(n)\)

>>> psequence([1,2,3]) < psequence([1,2,3])
False
>>> psequence([1,2,3]) < psequence([2,3,4])
True
>>> psequence([1,2,3]) < psequence([0,1,2])
False

Return type: bool

__mul__(times: int) → PSequence[T][source]¶

Repeat the sequence k times

\(O(\log{n}\log{k})\)

>>> psequence([1,2,3]) * 3
psequence([1, 2, 3, 1, 2, 3, 1, 2, 3])
>>> 3 * psequence([1,2,3])
psequence([1, 2, 3, 1, 2, 3, 1, 2, 3])

Parameters: times (int) –
Return type: PSequence[T]

__ne__(other) → bool[source]¶

Return self != other

\(O(n)\)

>>> psequence([1,2,3]) != psequence([1,2,3])
False
>>> psequence([1,2,3]) != psequence([2,3,4])
True

Return type: bool

static __new__(cls, _type, _size, _items)[source]¶

__reduce__()[source]¶

Support method for pickle

\(O(n)\)

>>> import pickle
>>> pickle.loads(pickle.dumps(psequence([1,2,3,4])))
psequence([1, 2, 3, 4])

__repr__() → str[source]¶

Get a formatted string representation

\(O(n)\)

>>> repr(psequence([1,2,3]))
'psequence([1, 2, 3])'

Return type: str

__reversed__() → Iterator[T][source]¶

Create a reverse iterator

\(O(1)\)

Iterating the entire sequence is \(O(n)\).

>>> i = reversed(psequence([1,2,3]))
>>> next(i)
3
>>> next(i)
2
>>> next(i)
1
>>> next(i)
Traceback (most recent call last):
...
StopIteration

Return type: Iterator[T]

__rmul__(times: int) → PSequence[T]¶

Repeat the sequence k times

\(O(\log{n}\log{k})\)

>>> psequence([1,2,3]) * 3
psequence([1, 2, 3, 1, 2, 3, 1, 2, 3])
>>> 3 * psequence([1,2,3])
psequence([1, 2, 3, 1, 2, 3, 1, 2, 3])

Parameters: times (int) –
Return type: PSequence[T]

__str__() → str¶

Get a formatted string representation

\(O(n)\)

>>> repr(psequence([1,2,3]))
'psequence([1, 2, 3])'

Return type: str

__weakref__¶: list of weak references to the object (if defined)

append(value: T) → PSequence[T]¶

Add an element to the right end

\(O(1)\)

>>> psequence([1,2,3]).append(4)
psequence([1, 2, 3, 4])
>>> psequence([1,2,3]).appendright(4)
psequence([1, 2, 3, 4])

Parameters: value (T) –
Return type: PSequence[T]

appendleft(value: T) → PSequence[T][source]¶

Add an element to the left end

\(O(1)\)

>>> psequence([1,2,3]).appendleft(0)
psequence([0, 1, 2, 3])

Parameters: value (T) –
Return type: PSequence[T]

appendright(value: T) → PSequence[T][source]¶

Add an element to the right end

\(O(1)\)

>>> psequence([1,2,3]).append(4)
psequence([1, 2, 3, 4])
>>> psequence([1,2,3]).appendright(4)
psequence([1, 2, 3, 4])

Parameters: value (T) –
Return type: PSequence[T]

chunksof(size: int) → PSequence[Sequence[T]][source]¶

Split the sequence into chunks

\(O(\frac{n}{k}\log{n})\)

>>> psequence([1,2,3,4,5,6,7,8]).chunksof(3)
psequence([psequence([1, 2, 3]), psequence([4, 5, 6]), psequence([7, 8])])

Parameters: size (int) –
Return type: PSequence[Sequence[T]]

count(value: T) → int[source]¶

Count the number of times a value appears

\(O(n)\)

>>> psequence([1,2,3,3,4]).count(3)
2

Parameters: value (T) –
Return type: int

delete(index: int) → PSequence[T][source]¶

delete(index: slice) → PSequence[T]

Delete the element(s) at the specified position(s)

Time complexities for n.delete(i):

\(O(\log(\min(i,n−i)))\) deleting a single item.
\(O(\log{n})\) deleting a contiguous slice.
\(O(\frac{n}{k}\log{k})\) deleting a non-contiguous slice.

Raises: IndexError – if the index is out of bounds

>>> psequence([1,2,3,4]).delete(2)
psequence([1, 2, 4])
>>> psequence([1,2,3,4,5]).delete(slice(1,4))
psequence([1, 5])
>>> psequence([1,2,3,4]).delete(5)
Traceback (most recent call last):
...
IndexError: ...

evolver() → Evolver[T][source]¶

Create an Evolver

\(O(1)\)

Return type: Evolver[T]

extend(other: Union[PSequence[T], Iterable[T]]) → PSequence[T]¶

Concatenate two sequences

\(O(\log(\min(n,k)))\) extend with PSequence

\(O(\log{n}+k)\) extend with iterable

>>> psequence([1,2]).extend([3,4])
psequence([1, 2, 3, 4])
>>> psequence([1,2]).extendright([3,4])
psequence([1, 2, 3, 4])
>>> psequence([1,2]) + [3,4]
psequence([1, 2, 3, 4])

Parameters: other (Union[PSequence[T], Iterable[T]]) –
Return type: PSequence[T]

extendleft(other: Union[PSequence[T], Iterable[T]]) → PSequence[T][source]¶

Concatenate two sequences

\(O(\log(\min(n,k)))\) extend with PSequence

\(O(\log{n}+k)\) extend with iterable

>>> psequence([1,2]).extendleft([3,4])
psequence([3, 4, 1, 2])

Parameters: other (Union[PSequence[T], Iterable[T]]) –
Return type: PSequence[T]

extendright(other: Union[PSequence[T], Iterable[T]]) → PSequence[T][source]¶

Concatenate two sequences

\(O(\log(\min(n,k)))\) extend with PSequence

\(O(\log{n}+k)\) extend with iterable

>>> psequence([1,2]).extend([3,4])
psequence([1, 2, 3, 4])
>>> psequence([1,2]).extendright([3,4])
psequence([1, 2, 3, 4])
>>> psequence([1,2]) + [3,4]
psequence([1, 2, 3, 4])

Parameters: other (Union[PSequence[T], Iterable[T]]) –
Return type: PSequence[T]

index(value, start: int = 0, stop: Optional[int] = None) → int[source]¶

Find the first index of a value

\(O(n)\)

Raises

ValueError – if the value is not in the sequence

Parameters

start (int) –
stop (Optional[int]) –

Return type

int

>>> psequence([1,2,3,4]).index(3)
2
>>> psequence([]).index(3)
Traceback (most recent call last):
...
ValueError: ...

insert(index: int, value: T) → PSequence[T][source]¶

Insert an element at the specified position

\(O(\log(\min(i,n−i)))\)

>>> psequence([1,2,3,4]).insert(2, 0)
psequence([1, 2, 0, 3, 4])
>>> psequence([1,2,3,4]).insert(-10, 0)
psequence([0, 1, 2, 3, 4])
>>> psequence([1,2,3,4]).insert(10, 0)
psequence([1, 2, 3, 4, 0])

Parameters

index (int) –
value (T) –

Return type

PSequence[T]

property left: T¶

Extract the first element

\(O(1)\)

Raises: IndexError – if the sequence is empty

>>> psequence([1,2,3,4]).left
1
>>> psequence([]).left
Traceback (most recent call last):
...
IndexError: ...

mset(*items: Union[int, T, Tuple[int, T]]) → PSequence[T][source]¶

Replace multiple elements

\(O(k\log{n}+k\log{k})\)

Raises: IndexError – if any index is out of bounds
Parameters: items (Union[int, T, Tuple[int, T]]) –
Return type: PSequence[T]

>>> psequence([1,2,3,4]).mset(2, 0, 3, 5)
psequence([1, 2, 0, 5])
>>> psequence([1,2,3,4]).mset((2, 0), (3, 5))
psequence([1, 2, 0, 5])
>>> psequence([1,2,3,4]).mset(5, 0)
Traceback (most recent call last):
...
IndexError: ...

remove(value: T) → PSequence[T][source]¶

Remove an element by value

\(O(n)\)

Raises: ValueError – if the value is not in the sequence
Parameters: value (T) –
Return type: PSequence[T]

>>> psequence([1,2,3,4]).remove(2)
psequence([1, 3, 4])
>>> psequence([1,2,3,4]).remove(0)
Traceback (most recent call last):
...
ValueError: ...

reverse() → PSequence[T][source]¶

Reverse the sequence

\(O(n)\)

>>> psequence([1,2,3,4]).reverse()
psequence([4, 3, 2, 1])

Return type: PSequence[T]

property right: T¶

Extract the last element

\(O(1)\)

Raises: IndexError – if the sequence is empty

>>> psequence([1,2,3,4]).right
4
>>> psequence([]).right
Traceback (most recent call last):
...
IndexError: ...

set(index: int, value: T) → PSequence[T][source]¶

set(index: slice, value: Iterable[T]) → PSequence[T]

Replace the element(s) at the specified position(s)

Time complexities for n.set(i,x):

\(O(\log(\min(i,n−i)))\) replacing a single item.
\(O(\log(\max(n,x)))\) replacing a contiguous slice.
\(O(x)\) replacing a non-contiguous slice.

Raises: IndexError – if the index is out of bounds

>>> psequence([1,2,3,4]).set(2, 0)
psequence([1, 2, 0, 4])
>>> psequence([1,2,3,4,5]).set(slice(1,4), [-1,-2,-3])
psequence([1, -1, -2, -3, 5])
>>> psequence([1,2,3,4]).set(5, 0)
Traceback (most recent call last):
...
IndexError: ...

sort(*args, **kwargs) → PSequence[T][source]¶

Creat a sorted copy of the sequence

\(O(n\log{n})\)

Arguments are the same as list.sort().

>>> psequence([3,1,4,2]).sort()
psequence([1, 2, 3, 4])

Return type: PSequence[T]

splitat(index: int) → Tuple[PSequence[T], PSequence[T]][source]¶

Split a sequence at a given position

\(O(\log(\min(i,n−i)))\)

Equivalent to (seq.take(i), seq.drop(i)). Does not raise IndexError, unlike view().

>>> psequence([1,2,3,4]).splitat(2)
(psequence([1, 2]), psequence([3, 4]))
>>> psequence([1,2,3,4]).splitat(5)
(psequence([1, 2, 3, 4]), psequence([]))
>>> psequence([1,2,3,4]).splitat(-1)
(psequence([1, 2, 3]), psequence([4]))
>>> psequence([1,2,3,4]).splitat(-5)
(psequence([]), psequence([1, 2, 3, 4]))

Parameters: index (int) –
Return type: Tuple[PSequence[T], PSequence[T]]

tolist() → List[T][source]¶

Convert the sequence to a list

\(O(n)\)

>>> psequence([1,2,3,4]).tolist()
[1, 2, 3, 4]

Return type: List[T]

totuple() → Tuple[T, ...][source]¶

Convert the sequence to a tuple

\(O(n)\)

>>> psequence([1,2,3,4]).totuple()
(1, 2, 3, 4)

Return type: Tuple[T, …]

transform(*transformations) → PSequence[T][source]¶

Apply one or more transformations

>>> from pyrsistent import ny
>>> psequence([1,2,3,4]).transform([ny], lambda x: x*2)
psequence([2, 4, 6, 8])

Return type: PSequence[T]

view(*index: int) → Tuple[Union[T, PSequence[T]], ...][source]¶

Split a sequence on the given position(s)

\(O(k\log{n})\)

Useful for pattern matching:

>>> 
... match seq.view(0, 1, 4):
...   case (_, x0, _, x1, x_2_3, x4, _, rest):
...     pass

Equivalent to (seq[:i1], seq[i1], seq[i1+1:i2], seq[i2], seq[i2+1:i3], ..., seq[in+1:]).

Raises: IndexError – if any index is out of bounds
Parameters: index (int) –
Return type: Tuple[Union[T, PSequence[T]], …]

>>> psequence([1,2,3,4]).view(0)
(psequence([]), 1, psequence([2, 3, 4]))
>>> psequence([1,2,3,4]).view(1)
(psequence([1]), 2, psequence([3, 4]))
>>> psequence([1,2,3,4]).view(1, 3)
(psequence([1]), 2, psequence([3]), 4, psequence([]))
>>> psequence([1,2,3,4]).view(5)
Traceback (most recent call last):
...
IndexError: ...

viewleft() → Tuple[T, PSequence[T]][source]¶

Analyse the left end

\(O(1)\)

Raises: IndexError – if the sequence is empty
Return type: Tuple[T, PSequence[T]]

>>> psequence([1,2,3,4]).viewleft()
(1, psequence([2, 3, 4]))
>>> psequence([]).viewleft()
Traceback (most recent call last):
...
IndexError: ...

viewright() → Tuple[PSequence[T], T][source]¶

Analyse the right end

\(O(1)\)

Raises: IndexError – if the sequence is empty
Return type: Tuple[PSequence[T], T]

>>> psequence([1,2,3,4]).viewright()
(psequence([1, 2, 3]), 4)
>>> psequence([]).viewright()
Traceback (most recent call last):
...
IndexError: ...

class pyrsistent_extras._psequence._python.Evolver[source]¶

Evolver for PSequence

The evolver acts as a mutable view of the sequence with “transaction like” semantics. No part of the underlying sequence is updated, it is still fully immutable. Furthermore multiple evolvers created from the same psequence do not interfere with each other.

You may want to use an evolver instead of working directly with PSequence in the following cases:

Multiple updates are done to the same sequence and the intermediate results are of no interest. In this case using an evolver may be easier to work with.
You need to pass a sequence into a legacy function or a function that you have no control over which performs in place mutations of lists. In this case pass an evolver instance instead and then create a new psequence from the evolver once the function returns.

The following example illustrates a typical workflow when working with evolvers:

Create the evolver and perform various mutating updates to it:

>>> seq1 = psequence([1,2,3,4,5])
>>> evo1 = seq1.evolver()
>>> evo1[1] = 22
>>> _ = evo1.append(6)
>>> _ = evo1.extend([7,8,9])
>>> evo1[8] += 1
>>> evo1
psequence([1, 22, 3, 4, 5, 6, 7, 8, 10]).evolver()

The underlying psequence remains the same:

>>> seq1
psequence([1, 2, 3, 4, 5])

The changes are kept in the evolver. An updated psequence can be created using the persistent() function on the evolver.

>>> seq2 = evo1.persistent()
>>> seq2
psequence([1, 22, 3, 4, 5, 6, 7, 8, 10])

The new psequence will share data with the original psequence in the same way that would have been done if only using operations on the sequence.

>>> evo = psequence([1,2,3,4]).evolver()
>>> evo[2] = 0
>>> evo
psequence([1, 2, 0, 4]).evolver()

__add__(other: Union[PSequence[T], Iterable[T]]) → Evolver[T][source]¶

Concatenate two sequences

\(O(\log(\min(n,k)))\) extend with PSequence

\(O(\log{n}+k)\) extend with iterable

>>> psequence([1,2]) + psequence([3,4])
psequence([1, 2, 3, 4])
>>> psequence([1,2]) + [3,4]
psequence([1, 2, 3, 4])

Parameters: other (Union[PSequence[T], Iterable[T]]) –
Return type: Evolver[T]

__delitem__(index)¶

Delete the element(s) at the specified position(s)

Time complexities for n.delete(i):

\(O(\log(\min(i,n−i)))\) deleting a single item.
\(O(\log{n})\) deleting a contiguous slice.
\(O(\frac{n}{k}\log{k})\) deleting a non-contiguous slice.

Raises: IndexError – if the index is out of bounds

>>> psequence([1,2,3,4]).delete(2)
psequence([1, 2, 4])
>>> psequence([1,2,3,4,5]).delete(slice(1,4))
psequence([1, 5])
>>> psequence([1,2,3,4]).delete(5)
Traceback (most recent call last):
...
IndexError: ...

__eq__(other) → bool[source]¶

Return self == other

\(O(n)\)

>>> psequence([1,2,3]) == psequence([1,2,3])
True
>>> psequence([1,2,3]) == psequence([2,3,4])
False

Return type: bool

__ge__(other) → bool[source]¶

Return self >= other

\(O(n)\)

>>> psequence([1,2,3]) >= psequence([1,2,3])
True
>>> psequence([1,2,3]) >= psequence([2,3,4])
False
>>> psequence([1,2,3]) >= psequence([0,1,2])
True

Return type: bool

__getitem__(index: int) → T[source]¶

__getitem__(index: slice) → PSequence[T]

Get the element(s) at the specified position(s)

Time complexities for n[i]:

\(O(\log(\min(i,n−i)))\) getting a single item.
\(O(\log(\max(i,m)))\) getting a contiguous slice.
\(O(\log{n}+m)\) getting a non-contiguous slice.

Raises: IndexError – if the index is out of bounds

>>> psequence([1,2,3,4])[2]
3
>>> psequence([1,2,3,4,5])[1:4]
psequence([2, 3, 4])
>>> psequence([1,2,3,4])[5]
Traceback (most recent call last):
...
IndexError: ...

__gt__(other) → bool[source]¶

Return self > other

\(O(n)\)

>>> psequence([1,2,3]) > psequence([1,2,3])
False
>>> psequence([1,2,3]) > psequence([2,3,4])
False
>>> psequence([1,2,3]) > psequence([0,1,2])
True

Return type: bool

__hash__ = None¶

__init__(_seq)[source]¶

classmethod __init_subclass__(*args, **kwargs)¶

This method is called when a class is subclassed.

The default implementation does nothing. It may be overridden to extend subclasses.

__iter__() → Iterator[T][source]¶

Create an iterator

\(O(1)\)

Iterating the entire sequence is \(O(n)\).

>>> i = iter(psequence([1,2,3]))
>>> next(i)
1
>>> next(i)
2
>>> next(i)
3
>>> next(i)
Traceback (most recent call last):
...
StopIteration

Return type: Iterator[T]

__le__(other) → bool[source]¶

Return self <= other

\(O(n)\)

>>> psequence([1,2,3]) <= psequence([1,2,3])
True
>>> psequence([1,2,3]) <= psequence([2,3,4])
True
>>> psequence([1,2,3]) <= psequence([0,1,2])
False

Return type: bool

__len__() → int[source]¶

Get the length of the sequence

\(O(1)\)

>>> len(psequence([1,2,3,4]))
4

Return type: int

__lt__(other) → bool[source]¶

Return self < other

\(O(n)\)

>>> psequence([1,2,3]) < psequence([1,2,3])
False
>>> psequence([1,2,3]) < psequence([2,3,4])
True
>>> psequence([1,2,3]) < psequence([0,1,2])
False

Return type: bool

__mul__(times: int) → Evolver[T][source]¶

Repeat the sequence k times

\(O(\log{n}\log{k})\)

>>> psequence([1,2,3]) * 3
psequence([1, 2, 3, 1, 2, 3, 1, 2, 3])
>>> 3 * psequence([1,2,3])
psequence([1, 2, 3, 1, 2, 3, 1, 2, 3])

Parameters: times (int) –
Return type: Evolver[T]

__ne__(other) → bool[source]¶

Return self != other

\(O(n)\)

>>> psequence([1,2,3]) != psequence([1,2,3])
False
>>> psequence([1,2,3]) != psequence([2,3,4])
True

Return type: bool

static __new__(cls, *args, **kwds)¶

__radd__(other: Union[PSequence[T], Iterable[T]]) → Evolver[T]¶

Concatenate two sequences

\(O(\log(\min(n,k)))\) extend with PSequence

\(O(\log{n}+k)\) extend with iterable

>>> psequence([1,2]) + psequence([3,4])
psequence([1, 2, 3, 4])
>>> psequence([1,2]) + [3,4]
psequence([1, 2, 3, 4])

Parameters: other (Union[PSequence[T], Iterable[T]]) –
Return type: Evolver[T]

__reduce__()[source]¶

Support method for pickle

\(O(n)\)

>>> import pickle
>>> pickle.loads(pickle.dumps(psequence([1,2,3,4])))
psequence([1, 2, 3, 4])

__repr__()[source]¶

Get a formatted string representation

\(O(n)\)

>>> repr(psequence([1,2,3]))
'psequence([1, 2, 3])'

__reversed__() → Iterator[T][source]¶

Create a reverse iterator

\(O(1)\)

Iterating the entire sequence is \(O(n)\).

>>> i = reversed(psequence([1,2,3]))
>>> next(i)
3
>>> next(i)
2
>>> next(i)
1
>>> next(i)
Traceback (most recent call last):
...
StopIteration

Return type: Iterator[T]

__rmul__(times: int) → Evolver[T]¶

Repeat the sequence k times

\(O(\log{n}\log{k})\)

>>> psequence([1,2,3]) * 3
psequence([1, 2, 3, 1, 2, 3, 1, 2, 3])
>>> 3 * psequence([1,2,3])
psequence([1, 2, 3, 1, 2, 3, 1, 2, 3])

Parameters: times (int) –
Return type: Evolver[T]

__setitem__(index, value)¶

Replace the element(s) at the specified position(s)

Time complexities for n.set(i,x):

\(O(\log(\min(i,n−i)))\) replacing a single item.
\(O(\log(\max(n,x)))\) replacing a contiguous slice.
\(O(x)\) replacing a non-contiguous slice.

Raises: IndexError – if the index is out of bounds

>>> psequence([1,2,3,4]).set(2, 0)
psequence([1, 2, 0, 4])
>>> psequence([1,2,3,4,5]).set(slice(1,4), [-1,-2,-3])
psequence([1, -1, -2, -3, 5])
>>> psequence([1,2,3,4]).set(5, 0)
Traceback (most recent call last):
...
IndexError: ...

__str__()¶

Get a formatted string representation

\(O(n)\)

>>> repr(psequence([1,2,3]))
'psequence([1, 2, 3])'

__weakref__¶: list of weak references to the object (if defined)

append(value: T) → Evolver[T]¶

Add an element to the right end

\(O(1)\)

>>> psequence([1,2,3]).append(4)
psequence([1, 2, 3, 4])
>>> psequence([1,2,3]).appendright(4)
psequence([1, 2, 3, 4])

Parameters: value (T) –
Return type: Evolver[T]

appendleft(value: T) → Evolver[T][source]¶

Add an element to the left end

\(O(1)\)

>>> psequence([1,2,3]).appendleft(0)
psequence([0, 1, 2, 3])

Parameters: value (T) –
Return type: Evolver[T]

appendright(value: T) → Evolver[T][source]¶

Add an element to the right end

\(O(1)\)

>>> psequence([1,2,3]).append(4)
psequence([1, 2, 3, 4])
>>> psequence([1,2,3]).appendright(4)
psequence([1, 2, 3, 4])

Parameters: value (T) –
Return type: Evolver[T]

chunksof(size: int) → PSequence[Sequence[T]][source]¶

Split the sequence into chunks

\(O(\frac{n}{k}\log{n})\)

>>> psequence([1,2,3,4,5,6,7,8]).chunksof(3)
psequence([psequence([1, 2, 3]), psequence([4, 5, 6]), psequence([7, 8])])

Parameters: size (int) –
Return type: PSequence[Sequence[T]]

clear() → Evolver[T][source]¶

Remove all items from the sequence

\(O(1)\)

>>> seq = psequence([1,2,3,4]).evolver()
>>> _ = seq.clear()
>>> seq
psequence([]).evolver()

Return type: Evolver[T]

copy() → Evolver[T][source]¶

Return a shallow copy of the sequence

\(O(1)\)

>>> seq1 = psequence([1,2,3,4]).evolver()
>>> seq2 = seq1.copy()
>>> seq2[1] = 0
>>> seq2
psequence([1, 0, 3, 4]).evolver()
>>> seq1
psequence([1, 2, 3, 4]).evolver()

Return type: Evolver[T]

count(value: T) → int[source]¶

Count the number of times a value appears

\(O(n)\)

>>> psequence([1,2,3,3,4]).count(3)
2

Parameters: value (T) –
Return type: int

delete(index: int) → Evolver[T][source]¶

delete(index: slice) → Evolver[T]

Delete the element(s) at the specified position(s)

Time complexities for n.delete(i):

\(O(\log(\min(i,n−i)))\) deleting a single item.
\(O(\log{n})\) deleting a contiguous slice.
\(O(\frac{n}{k}\log{k})\) deleting a non-contiguous slice.

Raises: IndexError – if the index is out of bounds

>>> psequence([1,2,3,4]).delete(2)
psequence([1, 2, 4])
>>> psequence([1,2,3,4,5]).delete(slice(1,4))
psequence([1, 5])
>>> psequence([1,2,3,4]).delete(5)
Traceback (most recent call last):
...
IndexError: ...

evolver() → Evolver[T]¶

Create an Evolver

\(O(1)\)

Return type: Evolver[T]

extend(other: Union[PSequence[T], Iterable[T]]) → Evolver[T]¶

Concatenate two sequences

\(O(\log(\min(n,k)))\) extend with PSequence

\(O(\log{n}+k)\) extend with iterable

>>> psequence([1,2]).extend([3,4])
psequence([1, 2, 3, 4])
>>> psequence([1,2]).extendright([3,4])
psequence([1, 2, 3, 4])
>>> psequence([1,2]) + [3,4]
psequence([1, 2, 3, 4])

Parameters: other (Union[PSequence[T], Iterable[T]]) –
Return type: Evolver[T]

extendleft(other: Union[PSequence[T], Iterable[T]]) → Evolver[T][source]¶

Concatenate two sequences

\(O(\log(\min(n,k)))\) extend with PSequence

\(O(\log{n}+k)\) extend with iterable

>>> psequence([1,2]).extendleft([3,4])
psequence([3, 4, 1, 2])

Parameters: other (Union[PSequence[T], Iterable[T]]) –
Return type: Evolver[T]

extendright(other: Union[PSequence[T], Iterable[T]]) → Evolver[T][source]¶

Concatenate two sequences

\(O(\log(\min(n,k)))\) extend with PSequence

\(O(\log{n}+k)\) extend with iterable

>>> psequence([1,2]).extend([3,4])
psequence([1, 2, 3, 4])
>>> psequence([1,2]).extendright([3,4])
psequence([1, 2, 3, 4])
>>> psequence([1,2]) + [3,4]
psequence([1, 2, 3, 4])

Parameters: other (Union[PSequence[T], Iterable[T]]) –
Return type: Evolver[T]

index(value, start: int = 0, stop: Optional[int] = None) → int[source]¶

Find the first index of a value

\(O(n)\)

Raises

ValueError – if the value is not in the sequence

Parameters

start (int) –
stop (Optional[int]) –

Return type

int

>>> psequence([1,2,3,4]).index(3)
2
>>> psequence([]).index(3)
Traceback (most recent call last):
...
ValueError: ...

insert(index: int, value: T) → Evolver[T][source]¶

Insert an element at the specified position

\(O(\log(\min(i,n−i)))\)

>>> psequence([1,2,3,4]).insert(2, 0)
psequence([1, 2, 0, 3, 4])
>>> psequence([1,2,3,4]).insert(-10, 0)
psequence([0, 1, 2, 3, 4])
>>> psequence([1,2,3,4]).insert(10, 0)
psequence([1, 2, 3, 4, 0])

Parameters

index (int) –
value (T) –

Return type

Evolver[T]

property left: T¶

Extract the first element

\(O(1)\)

Raises: IndexError – if the sequence is empty

>>> psequence([1,2,3,4]).left
1
>>> psequence([]).left
Traceback (most recent call last):
...
IndexError: ...

mset(*items: Union[int, T, Tuple[int, T]]) → Evolver[T][source]¶

Replace multiple elements

\(O(k\log{n}+k\log{k})\)

Raises: IndexError – if any index is out of bounds
Parameters: items (Union[int, T, Tuple[int, T]]) –
Return type: Evolver[T]

>>> psequence([1,2,3,4]).mset(2, 0, 3, 5)
psequence([1, 2, 0, 5])
>>> psequence([1,2,3,4]).mset((2, 0), (3, 5))
psequence([1, 2, 0, 5])
>>> psequence([1,2,3,4]).mset(5, 0)
Traceback (most recent call last):
...
IndexError: ...

persistent()[source]¶

Extract the sequence from the evolver

\(O(1)\)

>>> seq = psequence([1,2,3,4])
>>> seq.evolver().persistent()
psequence([1, 2, 3, 4])

pop(index: Optional[int] = None) → T[source]¶

pop(index: slice) → PSequence[T]

Remove and return an element at the specified index

See PSequence.delete and list.pop.

Raises: IndexError – if the sequence is empty or the index is out of bounds

>>> seq = psequence([1,2,3,4]).evolver()
>>> seq.pop()
4
>>> seq
psequence([1, 2, 3]).evolver()
>>> seq.pop(1)
2
>>> seq
psequence([1, 3]).evolver()

popleft() → T[source]¶

Remove the leftmost element

\(O(1)\)

Raises: IndexError – if the sequence is empty
Return type: T

>>> seq = psequence([1,2,3,4]).evolver()
>>> seq.popleft()
1
>>> seq
psequence([2, 3, 4]).evolver()
>>> psequence([]).evolver().popleft()
Traceback (most recent call last):
...
IndexError: ...

popright() → T[source]¶

Remove the rightmost element

\(O(1)\)

Raises: IndexError – if the sequence is empty
Return type: T

>>> seq = psequence([1,2,3,4]).evolver()
>>> seq.popright()
4
>>> seq
psequence([1, 2, 3]).evolver()
>>> psequence([]).evolver().popright()
Traceback (most recent call last):
...
IndexError: ...

remove(value: T) → Evolver[T][source]¶

Remove an element by value

\(O(n)\)

Raises: ValueError – if the value is not in the sequence
Parameters: value (T) –
Return type: Evolver[T]

>>> psequence([1,2,3,4]).remove(2)
psequence([1, 3, 4])
>>> psequence([1,2,3,4]).remove(0)
Traceback (most recent call last):
...
ValueError: ...

reverse() → Evolver[T][source]¶

Reverse the sequence

\(O(n)\)

>>> psequence([1,2,3,4]).reverse()
psequence([4, 3, 2, 1])

Return type: Evolver[T]

property right: T¶

Extract the last element

\(O(1)\)

Raises: IndexError – if the sequence is empty

>>> psequence([1,2,3,4]).right
4
>>> psequence([]).right
Traceback (most recent call last):
...
IndexError: ...

set(index: int, value: T) → Evolver[T][source]¶

set(index: slice, value: Iterable[T]) → Evolver[T]

Replace the element(s) at the specified position(s)

Time complexities for n.set(i,x):

\(O(\log(\min(i,n−i)))\) replacing a single item.
\(O(\log(\max(n,x)))\) replacing a contiguous slice.
\(O(x)\) replacing a non-contiguous slice.

Raises: IndexError – if the index is out of bounds

>>> psequence([1,2,3,4]).set(2, 0)
psequence([1, 2, 0, 4])
>>> psequence([1,2,3,4,5]).set(slice(1,4), [-1,-2,-3])
psequence([1, -1, -2, -3, 5])
>>> psequence([1,2,3,4]).set(5, 0)
Traceback (most recent call last):
...
IndexError: ...

sort(*args, **kwargs) → Evolver[T][source]¶

Creat a sorted copy of the sequence

\(O(n\log{n})\)

Arguments are the same as list.sort().

>>> psequence([3,1,4,2]).sort()
psequence([1, 2, 3, 4])

Return type: Evolver[T]

splitat(index: int) → Tuple[PSequence[T], PSequence[T]][source]¶

Split a sequence at a given position

\(O(\log(\min(i,n−i)))\)

Equivalent to (seq.take(i), seq.drop(i)). Does not raise IndexError, unlike view().

>>> psequence([1,2,3,4]).splitat(2)
(psequence([1, 2]), psequence([3, 4]))
>>> psequence([1,2,3,4]).splitat(5)
(psequence([1, 2, 3, 4]), psequence([]))
>>> psequence([1,2,3,4]).splitat(-1)
(psequence([1, 2, 3]), psequence([4]))
>>> psequence([1,2,3,4]).splitat(-5)
(psequence([]), psequence([1, 2, 3, 4]))

Parameters: index (int) –
Return type: Tuple[PSequence[T], PSequence[T]]

tolist() → List[T][source]¶

Convert the sequence to a list

\(O(n)\)

>>> psequence([1,2,3,4]).tolist()
[1, 2, 3, 4]

Return type: List[T]

totuple() → Tuple[T, ...][source]¶

Convert the sequence to a tuple

\(O(n)\)

>>> psequence([1,2,3,4]).totuple()
(1, 2, 3, 4)

Return type: Tuple[T, …]

transform(*transformations) → Evolver[T][source]¶

Apply one or more transformations

>>> from pyrsistent import ny
>>> psequence([1,2,3,4]).transform([ny], lambda x: x*2)
psequence([2, 4, 6, 8])

Return type: Evolver[T]

view(*index: int) → Tuple[Union[T, PSequence[T]], ...][source]¶

Split a sequence on the given position(s)

\(O(k\log{n})\)

Useful for pattern matching:

>>> 
... match seq.view(0, 1, 4):
...   case (_, x0, _, x1, x_2_3, x4, _, rest):
...     pass

Equivalent to (seq[:i1], seq[i1], seq[i1+1:i2], seq[i2], seq[i2+1:i3], ..., seq[in+1:]).

Raises: IndexError – if any index is out of bounds
Parameters: index (int) –
Return type: Tuple[Union[T, PSequence[T]], …]

>>> psequence([1,2,3,4]).view(0)
(psequence([]), 1, psequence([2, 3, 4]))
>>> psequence([1,2,3,4]).view(1)
(psequence([1]), 2, psequence([3, 4]))
>>> psequence([1,2,3,4]).view(1, 3)
(psequence([1]), 2, psequence([3]), 4, psequence([]))
>>> psequence([1,2,3,4]).view(5)
Traceback (most recent call last):
...
IndexError: ...

viewleft() → Tuple[T, PSequence[T]][source]¶

Analyse the left end

\(O(1)\)

Raises: IndexError – if the sequence is empty
Return type: Tuple[T, PSequence[T]]

>>> psequence([1,2,3,4]).viewleft()
(1, psequence([2, 3, 4]))
>>> psequence([]).viewleft()
Traceback (most recent call last):
...
IndexError: ...

viewright() → Tuple[PSequence[T], T][source]¶

Analyse the right end

\(O(1)\)

Raises: IndexError – if the sequence is empty
Return type: Tuple[PSequence[T], T]

>>> psequence([1,2,3,4]).viewright()
(psequence([1, 2, 3]), 4)
>>> psequence([]).viewright()
Traceback (most recent call last):
...
IndexError: ...