Lazy sequences of static length #
A lazy language's sequence is a stream of suspended elements behind one suspension,
LazySeq ε X = DomainResult ε (ℕ → DomainResult ε X). Its length is static: the language reads
it from the type, never from the stream, and it may be infinite (n : ℕ∞). Every operation
that builds a sequence writes bottom at and past that length (it masks), so the positions that
no program observes carry no information. Two masked sequences are equal exactly when their
elements below the length are.
LazySeq.index idemands the spine, then elementi.LazySeq.mk nreturns a stream masked atn. Its spine is available before any element is demanded (LazySeq.spine_mk).LazySeq.ofFn nreadsnelements by structural recursion,(List.ofFn xs).getD j ⊥, so at a concrete length the kernel evaluates each element at a closed index.LazySeq.mapandzipWithdemand the spines of their operands, then return a masked stream whose elements combine the operands' elements lazily.LazySeq.reindexandappendreturn a masked stream at once. Reading one of its elements demands the spine of the source it reads from, then one element of that source.LazySeq.encList enc xsis a native list as a lazy sequence. On these encodings the operations compute the correspondingListoperations (map_encList,zipWith_encList,reindex_id_encListforList.take,reindex_add_encListforList.drop, andappend_encList).LazySeq.decode n decreads a sequence of lengthnas a native family. It demands the spine, then the elements from left to right, and reads no position at or pastn. It decodes aboveencListwheneverdecdecodes aboveenc(DomainResult.DecodesAbove.lazySeq).LazySeq.spinedemands only the spine, andLazySeq.forceStepsforces a run of elements from left to right.
LazySeq.below n i decides i < n on ℕ∞ by cases, so masking computes. Recursive streams and
their productivity are in PolyFun.Control.Domain.PrefixRecursion.
Lazy sequences: a stream of suspended elements behind one suspension. The stream does not store a length; each operation takes the static length as an argument.
Equations
- LazySeq ε X = DomainResult ε (ℕ → DomainResult ε X)
Instances For
Positions below a length #
i < n, decided by cases on ℕ∞: every position is below ⊤.
Equations
- LazySeq.below none x✝ = true
- LazySeq.below (some n) x✝ = decide (x✝ < n)
Instances For
Construction and indexing #
Read element i: demand the spine, then the element.
Equations
- LazySeq.index i = DomainResult.bind (OmegaCompletePartialOrder.ContinuousHom.ofFun (fun (xs : ℕ → DomainResult ε X) => xs i) ⋯)
Instances For
Bottom at and past n.
Equations
- LazySeq.mask n = OmegaCompletePartialOrder.ContinuousHom.ofFun (fun (xs : ℕ → DomainResult ε X) (i : ℕ) => if LazySeq.below n i = true then xs i else ⊥) ⋯
Instances For
A stream masked at n, as a sequence whose spine is available at once.
Equations
Instances For
The elements of a list, then bottom.
Equations
- LazySeq.elems n = OmegaCompletePartialOrder.ContinuousHom.ofFun (fun (xs : Fin n → E) (j : ℕ) => (List.ofFn xs).getD j ⊥) ⋯
Instances For
n suspended elements as a sequence. Elements are read by structural recursion.
Equations
Instances For
Demand a sequence's spine and nothing else.
Equations
Instances For
The spine of a masked stream is available whatever its elements are.
Force k elements from position i on, from left to right, each by f.
Equations
- LazySeq.forceSteps f 0 x✝ = OmegaCompletePartialOrder.ContinuousHom.const (DomainResult.value { value := () })
- LazySeq.forceSteps f k.succ x✝ = OmegaCompletePartialOrder.ContinuousHom.ofFun (fun (xs : ℕ → DomainResult ε X) => (DomainResult.force (f (xs x✝))) ((LazySeq.forceSteps f k (x✝ + 1)) xs)) ⋯
Instances For
Elementwise operations and reindexing #
Apply f to each element below n, after demanding the spine.
Equations
- LazySeq.map n f = DomainResult.bind ((LazySeq.mk n).comp (OmegaCompletePartialOrder.ContinuousHom.ofFun (fun (xs : ℕ → DomainResult ε X) (i : ℕ) => f (xs i)) ⋯))
Instances For
Combine elements below n pairwise, after demanding the left spine, then the right one.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Read element f i of the source at position i, masked at n. The spine is returned at
once; reading an element demands the source's spine.
Equations
- LazySeq.reindex n f = (LazySeq.mk n).comp (OmegaCompletePartialOrder.ContinuousHom.ofFun (fun (v : LazySeq ε X) (i : ℕ) => (LazySeq.index (f i)) v) ⋯)
Instances For
xs ++ ys with a front of length front, masked at n. Position i reads element i of
xs below front and element i - front of ys from there on. The spine is returned at once;
reading an element demands the spine of the operand it comes from.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Encodings of native lists #
A native list as a lazy sequence: each element encoded below the length, bottom past it.
Equations
- LazySeq.encList enc xs = DomainResult.value fun (i : ℕ) => if h : i < xs.length then enc xs[i] else ⊥
Instances For
An encoding lies below a returned stream exactly when each element's encoding lies below the stream's element at its position.
Injective encodings that never diverge give injective list encodings.
A constant stream masked at n is the encoding of n copies.
Mapping over an encoding below its length is the encoding of the mapped list.
Combining two encodings of one length pairwise is the encoding of the zipped list.
Taking a prefix of an encoded list is the encoded prefix.
Dropping a prefix of an encoded list is the encoded suffix.
Appending encoded lists is the encoded append.
Decoding a sequence of static length #
Read a sequence of length n as a native family: demand the spine, then decode elements 0
to n - 1 from left to right. The first element that does not decode to a value gives the
result, and no position at or past n is read.
Equations
- LazySeq.decode n dec d = DomainResult.bindPlain d fun (xs : ℕ → DomainResult ε X) => Fin.mOfFn n fun (i : Fin n) => dec (xs ↑i)
Instances For
A sequence decodes to g exactly when it returns a stream whose elements below n decode to
the matching values of g.
Decoding a sequence of length n element by element decodes above the encoding of native
families as lists.