Documentation

PolyFun.Control.Domain.LazySeq

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.below n i decides i < n on ℕ∞ by cases, so masking computes. Recursive streams and their productivity are in PolyFun.Control.Domain.PrefixRecursion.

@[reducible, inline]
abbrev LazySeq (ε : Type u_1) (X : Type u_2) :
Type (max u_1 u_2)

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

    Positions below a length #

    i < n, decided by cases on ℕ∞: every position is below ⊤.

    Equations
    Instances For
      @[simp]
      theorem LazySeq.below_natCast (n i : ℕ) :
      below (↑n) i = decide (i < n)
      @[simp]
      theorem LazySeq.below_top (i : ℕ) :
      @[simp]
      theorem LazySeq.below_zero (i : ℕ) :
      @[simp]
      theorem LazySeq.below_one (i : ℕ) :
      below 1 i = decide (i < 1)
      theorem LazySeq.below_eq_true_iff {n : ℕ∞} {i : ℕ} :
      below n i = true ↔ ↑i < n

      below decides the order of ℕ∞.

      theorem LazySeq.below_of_lt {n : ℕ∞} {i j : ℕ} (hi : below n i = true) (hj : j < i) :

      Positions before a position below n are below n.

      Construction and indexing #

      noncomputable def LazySeq.index {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (i : ℕ) :

      Read element i: demand the spine, then the element.

      Equations
      Instances For
        @[simp]
        theorem LazySeq.index_value {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (i : ℕ) (xs : ℕ → DomainResult ε X) :
        (index i) (DomainResult.value xs) = xs i
        @[simp]
        theorem LazySeq.index_bot {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (i : ℕ) :
        @[simp]
        theorem LazySeq.index_error {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (i : ℕ) (e : ε) :
        noncomputable def LazySeq.mask {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (n : ℕ∞) :

        Bottom at and past n.

        Equations
        Instances For
          theorem LazySeq.mask_apply {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (n : ℕ∞) (xs : ℕ → DomainResult ε X) (i : ℕ) :
          (mask n) xs i = if below n i = true then xs i else ⊥
          noncomputable def LazySeq.mk {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (n : ℕ∞) :

          A stream masked at n, as a sequence whose spine is available at once.

          Equations
          Instances For
            theorem LazySeq.mk_apply {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (n : ℕ∞) (xs : ℕ → DomainResult ε X) :
            (mk n) xs = DomainResult.value fun (i : ℕ) => if below n i = true then xs i else ⊥
            theorem LazySeq.index_mk {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (n : ℕ∞) (xs : ℕ → DomainResult ε X) (i : ℕ) :
            (index i) ((mk n) xs) = if below n i = true then xs i else ⊥
            @[simp]
            theorem LazySeq.index_mk_of_below {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] {n : ℕ∞} (xs : ℕ → DomainResult ε X) {i : ℕ} (hi : below n i = true) :
            (index i) ((mk n) xs) = xs i
            @[simp]
            theorem LazySeq.index_mk_of_not_below {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] {n : ℕ∞} (xs : ℕ → DomainResult ε X) {i : ℕ} (hi : below n i = false) :
            (index i) ((mk n) xs) = ⊥
            noncomputable def LazySeq.elems {E : Type u_3} [OmegaCompletePartialOrder E] [OrderBot E] (n : ℕ) :
            (Fin n → E) →𝒄 ℕ → E

            The elements of a list, then bottom.

            Equations
            Instances For
              theorem LazySeq.elems_apply {E : Type u_3} [OmegaCompletePartialOrder E] [OrderBot E] (n : ℕ) (xs : Fin n → E) (j : ℕ) :
              (elems n) xs j = if h : j < n then xs ⟨j, h⟩ else ⊥
              noncomputable def LazySeq.ofFn {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (n : ℕ) :
              (Fin n → DomainResult ε X) →𝒄 LazySeq ε X

              n suspended elements as a sequence. Elements are read by structural recursion.

              Equations
              Instances For
                theorem LazySeq.ofFn_apply {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (n : ℕ) (xs : Fin n → DomainResult ε X) :
                (ofFn n) xs = DomainResult.value ((elems n) xs)
                theorem LazySeq.ofFn_eq_mk {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (n : ℕ) (xs : Fin n → DomainResult ε X) :
                (ofFn n) xs = (mk ↑n) fun (j : ℕ) => if h : j < n then xs ⟨j, h⟩ else ⊥
                noncomputable def LazySeq.spine {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] :

                Demand a sequence's spine and nothing else.

                Equations
                Instances For
                  @[simp]
                  theorem LazySeq.spine_value {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (xs : ℕ → DomainResult ε X) :
                  @[simp]
                  theorem LazySeq.spine_mk {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (n : ℕ∞) (xs : ℕ → DomainResult ε X) :
                  spine ((mk n) xs) = DomainResult.value { value := () }

                  The spine of a masked stream is available whatever its elements are.

                  @[simp]

                  Force k elements from position i on, from left to right, each by f.

                  Equations
                  Instances For
                    @[simp]
                    theorem LazySeq.forceSteps_zero {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (f : DomainResult ε X →𝒄 DomainResult ε (DiscreteOrder Unit)) (i : ℕ) (xs : ℕ → DomainResult ε X) :
                    (forceSteps f 0 i) xs = DomainResult.value { value := () }
                    theorem LazySeq.forceSteps_succ {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (f : DomainResult ε X →𝒄 DomainResult ε (DiscreteOrder Unit)) (k i : ℕ) (xs : ℕ → DomainResult ε X) :
                    (forceSteps f (k + 1) i) xs = (DomainResult.force (f (xs i))) ((forceSteps f k (i + 1)) xs)

                    Elementwise operations and reindexing #

                    noncomputable def LazySeq.map {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] {Y : Type u_3} [OmegaCompletePartialOrder Y] (n : ℕ∞) (f : DomainResult ε X →𝒄 DomainResult ε Y) :

                    Apply f to each element below n, after demanding the spine.

                    Equations
                    Instances For
                      theorem LazySeq.map_value {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] {Y : Type u_3} [OmegaCompletePartialOrder Y] (n : ℕ∞) (f : DomainResult ε X →𝒄 DomainResult ε Y) (xs : ℕ → DomainResult ε X) :
                      (map n f) (DomainResult.value xs) = (mk n) fun (i : ℕ) => f (xs i)
                      noncomputable def LazySeq.zipWith {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] {Y : Type u_3} {Z : Type u_4} [OmegaCompletePartialOrder Y] [OmegaCompletePartialOrder Z] (n : ℕ∞) (f : DomainResult ε X →𝒄 DomainResult ε Y →𝒄 DomainResult ε Z) :

                      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
                        theorem LazySeq.zipWith_value {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] {Y : Type u_3} {Z : Type u_4} [OmegaCompletePartialOrder Y] [OmegaCompletePartialOrder Z] (n : ℕ∞) (f : DomainResult ε X →𝒄 DomainResult ε Y →𝒄 DomainResult ε Z) (xs : ℕ → DomainResult ε X) (ys : ℕ → DomainResult ε Y) :
                        ((zipWith n f) (DomainResult.value xs)) (DomainResult.value ys) = (mk n) fun (i : ℕ) => (f (xs i)) (ys i)
                        noncomputable def LazySeq.reindex {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (n : ℕ∞) (f : ℕ → ℕ) :

                        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
                        Instances For
                          theorem LazySeq.reindex_apply {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (n : ℕ∞) (f : ℕ → ℕ) (v : LazySeq ε X) :
                          (reindex n f) v = (mk n) fun (i : ℕ) => (index (f i)) v
                          noncomputable def LazySeq.append {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (front : ℕ) (n : ℕ∞) :

                          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
                            theorem LazySeq.append_apply {ε : Type u_1} {X : Type u_2} [OmegaCompletePartialOrder X] (front : ℕ) (n : ℕ∞) (xs ys : LazySeq ε X) :
                            ((append front n) xs) ys = (mk n) fun (i : ℕ) => if i < front then (index i) xs else (index (i - front)) ys

                            Encodings of native lists #

                            noncomputable def LazySeq.encList {ε : Type u_1} {X : Type u_2} {β : Type u_3} (enc : β → DomainResult ε X) (xs : List β) :
                            LazySeq ε X

                            A native list as a lazy sequence: each element encoded below the length, bottom past it.

                            Equations
                            Instances For
                              theorem LazySeq.encList_le_value_iff {ε : Type u_1} {X : Type u_2} {β : Type u_3} [Preorder X] (enc : β → DomainResult ε X) (ys : List β) (xs : ℕ → DomainResult ε X) :
                              encList enc ys ≤ DomainResult.value xs ↔ ∀ (i : ℕ) (hi : i < ys.length), enc ys[i] ≤ xs i

                              An encoding lies below a returned stream exactly when each element's encoding lies below the stream's element at its position.

                              theorem LazySeq.encList_ofFn_le_value_iff {ε : Type u_1} {X : Type u_2} {β : Type u_3} [Preorder X] {n : ℕ} (enc : β → DomainResult ε X) (ys : Fin n → β) (xs : ℕ → DomainResult ε X) :
                              encList enc (List.ofFn ys) ≤ DomainResult.value xs ↔ ∀ (i : Fin n), enc (ys i) ≤ xs ↑i
                              theorem LazySeq.index_encList {ε : Type u_1} {X : Type u_2} {β : Type u_3} [OmegaCompletePartialOrder X] (enc : β → DomainResult ε X) (xs : List β) (i : ℕ) (h : i < xs.length) :
                              (index i) (encList enc xs) = enc xs[i]
                              theorem LazySeq.index_encList_of_le {ε : Type u_1} {X : Type u_2} {β : Type u_3} [OmegaCompletePartialOrder X] (enc : β → DomainResult ε X) (xs : List β) (i : ℕ) (h : xs.length ≤ i) :
                              (index i) (encList enc xs) = ⊥
                              theorem LazySeq.encList_eq_mk {ε : Type u_1} {X : Type u_2} {β : Type u_3} [OmegaCompletePartialOrder X] (enc : β → DomainResult ε X) (xs : List β) :
                              encList enc xs = (mk ↑xs.length) fun (i : ℕ) => if h : i < xs.length then enc xs[i] else ⊥

                              An encoding is a masked stream at the list's length.

                              theorem LazySeq.encList_injective {ε : Type u_1} {X : Type u_2} {β : Type u_3} [OmegaCompletePartialOrder X] {enc : β → DomainResult ε X} (henc : Function.Injective enc) (hbot : ∀ (x : β), enc x ≠ ⊥) :

                              Injective encodings that never diverge give injective list encodings.

                              theorem LazySeq.mk_const_eq_encList_replicate {ε : Type u_1} {X : Type u_2} {β : Type u_3} [OmegaCompletePartialOrder X] (enc : β → DomainResult ε X) (n : ℕ) (v : β) :
                              ((mk ↑n) fun (x : ℕ) => enc v) = encList enc (List.replicate n v)

                              A constant stream masked at n is the encoding of n copies.

                              theorem LazySeq.map_encList {ε : Type u_1} {X : Type u_2} {β : Type u_3} {γ : Type u_4} [OmegaCompletePartialOrder X] {Y : Type u_6} [OmegaCompletePartialOrder Y] (encX : β → DomainResult ε X) (encY : γ → DomainResult ε Y) (f : DomainResult ε X →𝒄 DomainResult ε Y) (g : β → γ) (hf : ∀ (x : β), f (encX x) = encY (g x)) (xs : List β) :
                              (map (↑xs.length) f) (encList encX xs) = encList encY (List.map g xs)

                              Mapping over an encoding below its length is the encoding of the mapped list.

                              theorem LazySeq.zipWith_encList {ε : Type u_1} {X : Type u_2} {β : Type u_3} {γ : Type u_4} {δ : Type u_5} [OmegaCompletePartialOrder X] {Y : Type u_6} {Z : Type u_7} [OmegaCompletePartialOrder Y] [OmegaCompletePartialOrder Z] (encX : β → DomainResult ε X) (encY : γ → DomainResult ε Y) (encZ : δ → DomainResult ε Z) (f : DomainResult ε X →𝒄 DomainResult ε Y →𝒄 DomainResult ε Z) (g : β → γ → δ) (hf : ∀ (x : β) (y : γ), (f (encX x)) (encY y) = encZ (g x y)) (xs : List β) (ys : List γ) (hlen : xs.length = ys.length) :
                              ((zipWith (↑xs.length) f) (encList encX xs)) (encList encY ys) = encList encZ (List.zipWith g xs ys)

                              Combining two encodings of one length pairwise is the encoding of the zipped list.

                              theorem LazySeq.reindex_id_encList {ε : Type u_1} {X : Type u_2} {β : Type u_3} [OmegaCompletePartialOrder X] (enc : β → DomainResult ε X) (xs : List β) (front : ℕ) :
                              (reindex (↑front) id) (encList enc xs) = encList enc (List.take front xs)

                              Taking a prefix of an encoded list is the encoded prefix.

                              theorem LazySeq.reindex_add_encList {ε : Type u_1} {X : Type u_2} {β : Type u_3} [OmegaCompletePartialOrder X] (enc : β → DomainResult ε X) (xs : List β) (front : ℕ) :
                              (reindex ↑(xs.length - front) fun (i : ℕ) => front + i) (encList enc xs) = encList enc (List.drop front xs)

                              Dropping a prefix of an encoded list is the encoded suffix.

                              theorem LazySeq.append_encList {ε : Type u_1} {X : Type u_2} {β : Type u_3} [OmegaCompletePartialOrder X] (enc : β → DomainResult ε X) (l r : List β) :
                              ((append l.length ↑(l.length + r.length)) (encList enc l)) (encList enc r) = encList enc (l ++ r)

                              Appending encoded lists is the encoded append.

                              Decoding a sequence of static length #

                              def LazySeq.decode {ε : Type u_1} {X : Type u_2} {N : Type u_3} (n : ℕ) (dec : DomainResult ε X → DomainResult ε N) (d : LazySeq ε X) :
                              DomainResult ε (Fin n → N)

                              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
                              Instances For
                                @[simp]
                                theorem LazySeq.decode_bot {ε : Type u_1} {X : Type u_2} {N : Type u_3} (n : ℕ) (dec : DomainResult ε X → DomainResult ε N) :
                                decode n dec ⊥ = ⊥
                                @[simp]
                                theorem LazySeq.decode_error {ε : Type u_1} {X : Type u_2} {N : Type u_3} (n : ℕ) (dec : DomainResult ε X → DomainResult ε N) (e : ε) :
                                theorem LazySeq.decode_value {ε : Type u_1} {X : Type u_2} {N : Type u_3} (n : ℕ) (dec : DomainResult ε X → DomainResult ε N) (xs : ℕ → DomainResult ε X) :
                                decode n dec (DomainResult.value xs) = Fin.mOfFn n fun (i : Fin n) => dec (xs ↑i)
                                theorem LazySeq.decode_eq_value_iff {ε : Type u_1} {X : Type u_2} {N : Type u_3} {n : ℕ} {dec : DomainResult ε X → DomainResult ε N} {d : LazySeq ε X} {g : Fin n → N} :
                                decode n dec d = DomainResult.value g ↔ ∃ (xs : ℕ → DomainResult ε X), d = DomainResult.value xs ∧ ∀ (i : Fin n), dec (xs ↑i) = DomainResult.value (g i)

                                A sequence decodes to g exactly when it returns a stream whose elements below n decode to the matching values of g.

                                theorem DomainResult.DecodesAbove.lazySeq {ε : Type u_1} {X : Type u_2} {N : Type u_3} [Preorder X] {enc : N → DomainResult ε X} {dec : DomainResult ε X → DomainResult ε N} (h : DecodesAbove enc dec) (n : ℕ) :
                                DecodesAbove (fun (xs : Fin n → N) => LazySeq.encList enc (List.ofFn xs)) (LazySeq.decode n dec)

                                Decoding a sequence of length n element by element decodes above the encoding of native families as lists.