slicecompose 0.2.0

Exact composition of Python slices

slicecompose

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

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

• 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]: the last element
slice(None, -2, -1)

>>> 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

>>> compose(slice(2, None, -1), slice(None, 2), slice(None, -1))  # k-ary
slice(2, 0, -2)

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. Where several slices are equivalent, compose returns one of them: in the second example it picks [:-2:-1], which selects the last element just like [-1:]. 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(*slices) -> slice | None

The core decision procedure described above, for any number of slices. Accepts any valid slice objects, including huge field values (no ranges are ever materialized; everything is decided arithmetically). The k-ary form is strictly stronger than iterated pairwise composition: in the last example above, neither adjacent pair is expressible on its own — only the whole triple is, and no sequence of pairwise merges can discover that.

SliceChain(*slices)

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

• On construction the chain is reduced to a minimal-length equivalent chain: every contiguous sub-chain's expressibility is decided directly with the k-ary compose and a shortest partition into expressible blocks is chosen (e.g. [::2], [::-1], [::-1] reduces to [::2]).
• .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'

Because sub-chains are decided directly (never by searching merge orders), the result is order-free and also covers reductions that are invisible to pairwise merging — chains where no adjacent pair merges but a longer block does. See EXPLANATION.md §§7–8 for the theory and verified examples.

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