slicecompose 0.1.0

Exact composition of Python slices

slicecompose

Exact composition of Python slices — pure Python, standard library only.

compose(s1, s2) returns a slice s3 such that arr[s1][s2] == arr[s3] for every sequence arr (every length, including 0), or None if no such slice exists. Both directions of the decision are exact:

• Sound — a returned slice is equivalent for all lengths, not just tested ones.
• Complete — None is returned only when no equivalent single slice exists.

>>> from slicecompose import compose, SliceChain

>>> compose(slice(2, None), slice(3, None))          # arr[2:][3:] == arr[5:]
slice(5, None, None)

>>> compose(slice(None, None, -1), slice(None, 1))   # arr[::-1][:1] == arr[-1:]
slice(-1, None, None)

>>> compose(slice(-2, None), slice(None, 1))         # arr[-2:][:1] == arr[-2::2]
slice(-2, None, 2)

>>> compose(slice(None, None, 2), slice(None, None, -1)) is None
True

The last pair really has no equivalent: arr[::2][::-1] starts at index n-1 for odd n but n-2 for even n, and no fixed slice can depend on the parity of the length. The third example shows the opposite surprise: the result must select the single element at index max(0, n-2), which no "obvious" candidate like [-2:-1] does (it is empty at n == 1) — but [-2::2] does, for every n.

Why this is harder than plugging into slice.indices(): the answer must be a fixed slice that works universally, without knowing the length of the sequence it will be applied to. Clamping, negative indices, and the sign-dependent defaults make the composed selection a piecewise function of the length; compose decides exactly whether that function is realizable by a single slice.

API

compose(s1, s2) -> slice | None

The core decision procedure described above. Accepts any valid slice objects, including huge field values (no ranges are ever materialized; everything is decided arithmetically).

SliceChain(*slices)

Container for a sequence of slices applied in order, e.g. seq[s0][s1]...[sk].

• On construction, adjacent pairs are merged with compose until no adjacent pair merges; a successful merge is retried against its new left neighbor, so cascading reductions are found (e.g. [::2], [::-1], [::-1] reduces to [::2] — the last two merge first).
• .slices — the reduced tuple of slices.
• .apply(seq) — applies the (reduced) slices in order; correct whether or not any merging happened.

>>> ch = SliceChain(slice(None, None, 2), slice(None, None, -1), slice(None, None, -1))
>>> ch.slices
(slice(None, None, 2),)
>>> SliceChain(slice(2, None), slice(3, None)).apply("abcdefgh")
'fgh'

Note that the reduced chain is a fixpoint of adjacent-pair merging, not necessarily the shortest one: pairwise reduction is not confluent, and there are chains whose total effect is a single slice even though no adjacent pair merges at all. See EXPLANATION.md §7 for verified examples and details.

SlicePlan / s_

Lazy plan building with ordinary bracket notation. s_ is the ready-made empty plan; slicing a plan returns a new plan (the original is unchanged), and nothing is computed while slices are gathered. On the first query — .slices, .slice, .apply(seq), ==/hash — the plan reduces its stored chain in place and remembers that it did, so the reduction runs at most once per batch of gathered slices.

>>> from slicecompose import s_
>>> s_[2:][3:].slice
slice(5, None, None)
>>> plan = s_[100:]
>>> plan[::2].slices                  # branching; plan itself is unchanged
(slice(100, None, 2),)
>>> s_[::2][::-1].slice is None       # irreducible pairs stay a chain
True
>>> s_[::2][::-1].apply(tuple(range(9)))
(8, 6, 4, 2, 0)

This is aimed at expensive media (video streams, remote arrays): build the access plan symbolically with normal slicing syntax, reduce it, and only then touch the data. A reduced slice needs no length to be executed — its anchors are only "offset from the front" and "offset from the end" — so the plan works even when the element count is unknown or unreliable.

Correctness

EXPLANATION.md contains the full argument for why the implementation is sound and complete for every length — the infinite quantification over n is reduced to finitely many exact checks (regime breakpoints, per-stretch staircase/sawtooth normal forms, an exact verifier, and profile-forced candidate generation). Returned slices are always validated by the exact verifier, so soundness does not rest on the candidate generator.

The test suite (test_slicecompose.py) additionally audits both failure modes empirically: exhaustive small-field grids checked for wrong merges by brute force and for missed merges against large candidate tables, huge-field randomized soundness checks, structural consistency probes, and the problem statement's examples.

Installation

pip install slicecompose      # from PyPI, once published
pip install .                 # from a checkout

Pure Python, no dependencies.

Running the tests

pytest                        # quick tier, ~30 s
SLICECOMPOSE_FULL=1 pytest    # exhaustive grids, ~35 min

verify_examples.py independently re-checks the examples claimed in PROBLEM.md by direct evaluation.

Files

file	contents
src/slicecompose/	the library (compose, SlicePlan/s_, SliceChain)
tests/test_slicecompose.py	test suite (quick and exhaustive tiers)
PROBLEM.md	the problem statement
EXPLANATION.md	soundness/completeness argument
verify_examples.py	standalone check of the problem's examples