Definition of Stream' and functions on streams

A stream Stream' α is an infinite sequence of elements of α. One can also think about it as an infinite list. In this file we define Stream' and some functions that take and/or return streams. Note that we already have Stream to represent a similar object, hence the awkward naming.

def Stream' (α : Type u) : Type u

A stream Stream' α is an infinite sequence of elements of α.

Equations

• Stream' α = (ℕ → α)

def Stream'.cons {α : Type u_1} (a : α) (s : Stream' α) : Stream' α

Prepend an element to a stream.

Equations

• Stream'.cons a s x = match x with | 0 => a | Nat.succ n => s n

def Stream'.«term_::_» : Lean.TrailingParserDescr

Equations

• Stream'.«term_::_» = Lean.ParserDescr.trailingNode `Stream'.term_::_ 67 68 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " :: ") (Lean.ParserDescr.cat `term 67))

def Stream'.get {α : Type u_1} (s : Stream' α) (n : ℕ) : α

Get the n-th element of a stream.

Equations

• Stream'.get s n = s n

@[inline, reducible]

abbrev Stream'.head {α : Type u_1} (s : Stream' α) : α

Head of a stream: Stream'.head s = Stream'.get s 0.

Equations

• Stream'.head s = Stream'.get s 0

def Stream'.tail {α : Type u_1} (s : Stream' α) : Stream' α

Tail of a stream: Stream'.tail (h :: t) = t.

Equations

• Stream'.tail s i = Stream'.get s (i + 1)

def Stream'.drop {α : Type u_1} (n : ℕ) (s : Stream' α) : Stream' α

Drop first n elements of a stream.

Equations

• Stream'.drop n s i = Stream'.get s (i + n)

def Stream'.All {α : Type u_1} (p : α → Prop) (s : Stream' α) : Prop

Proposition saying that all elements of a stream satisfy a predicate.

Equations

• Stream'.All p s = ∀ (n : ℕ), p (Stream'.get s n)

def Stream'.Any {α : Type u_1} (p : α → Prop) (s : Stream' α) : Prop

Proposition saying that at least one element of a stream satisfies a predicate.

Equations

• Stream'.Any p s = ∃ (n : ℕ), p (Stream'.get s n)

instance Stream'.instMembershipStream' {α : Type u_1} : Membership α (Stream' α)

a ∈ s means that a = Stream'.get n s for some n.

Equations

• Stream'.instMembershipStream' = { mem := fun (a : α) (s : Stream' α) => Stream'.Any (fun (b : α) => a = b) s }

def Stream'.map {α : Type u_1} {β : Type u_2} (f : α → β) (s : Stream' α) : Stream' β

Apply a function f to all elements of a stream s.

Equations

• Stream'.map f s n = f (Stream'.get s n)

def Stream'.zip {α : Type u_1} {β : Type u_2} {δ : Type u_3} (f : α → β → δ) (s₁ : Stream' α) (s₂ : Stream' β) : Stream' δ

Zip two streams using a binary operation: Stream'.get n (Stream'.zip f s₁ s₂) = f (Stream'.get s₁) (Stream'.get s₂).

Equations

• Stream'.zip f s₁ s₂ n = f (Stream'.get s₁ n) (Stream'.get s₂ n)

def Stream'.enum {α : Type u_1} (s : Stream' α) : Stream' (ℕ × α)

Enumerate a stream by tagging each element with its index.

Equations

• Stream'.enum s n = (n, Stream'.get s n)

def Stream'.const {α : Type u_1} (a : α) : Stream' α

The constant stream: Stream'.get n (Stream'.const a) = a.

Equations

• Stream'.const a x = a

def Stream'.iterate {α : Type u_1} (f : α → α) (a : α) : Stream' α

Iterates of a function as a stream.

Equations

• Stream'.iterate f a 0 = a
• Stream'.iterate f a (Nat.succ n) = f (Stream'.iterate f a n)

def Stream'.corec {α : Type u_1} {β : Type u_2} (f : α → β) (g : α → α) : α → Stream' β

Equations

• Stream'.corec f g a = Stream'.map f (Stream'.iterate g a)

def Stream'.corecOn {α : Type u_1} {β : Type u_2} (a : α) (f : α → β) (g : α → α) : Stream' β

Equations

• Stream'.corecOn a f g = Stream'.corec f g a

def Stream'.corec' {α : Type u_1} {β : Type u_2} (f : α → β × α) : α → Stream' β

Equations

• Stream'.corec' f = Stream'.corec (Prod.fst ∘ f) (Prod.snd ∘ f)

def Stream'.corecState {σ : Type u_1} {α : Type u_1} (cmd : StateM σ α) (s : σ) : Stream' α

Use a state monad to generate a stream through corecursion

Equations

• Stream'.corecState cmd s = Stream'.corec Prod.fst (StateT.run cmd ∘ Prod.snd) (StateT.run cmd s)

@[inline, reducible]

abbrev Stream'.unfolds {α : Type u_1} {β : Type u_2} (g : α → β) (f : α → α) (a : α) : Stream' β

Equations

• Stream'.unfolds g f a = Stream'.corec g f a

def Stream'.interleave {α : Type u_1} (s₁ : Stream' α) (s₂ : Stream' α) : Stream' α

Interleave two streams.

Equations

• One or more equations did not get rendered due to their size.

def Stream'.«term_⋈_» : Lean.TrailingParserDescr

Equations

• Stream'.«term_⋈_» = Lean.ParserDescr.trailingNode `Stream'.term_⋈_ 65 65 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ⋈ ") (Lean.ParserDescr.cat `term 66))

def Stream'.even {α : Type u_1} (s : Stream' α) : Stream' α

Elements of a stream with even indices.

Equations

• Stream'.even s = Stream'.corec (fun (s : Stream' α) => Stream'.head s) (fun (s : Stream' α) => Stream'.tail (Stream'.tail s)) s

def Stream'.odd {α : Type u_1} (s : Stream' α) : Stream' α

Elements of a stream with odd indices.

Equations

• Stream'.odd s = Stream'.even (Stream'.tail s)

def Stream'.appendStream' {α : Type u_1} : List α → Stream' α → Stream' α

Append a stream to a list.

Equations

• [] ++ₛ x = x
• a :: l ++ₛ x = Stream'.cons a (l ++ₛ x)

def Stream'.«term_++ₛ_» : Lean.TrailingParserDescr

Equations

• Stream'.«term_++ₛ_» = Lean.ParserDescr.trailingNode `Stream'.term_++ₛ_ 65 65 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ++ₛ ") (Lean.ParserDescr.cat `term 66))

def Stream'.take {α : Type u_1} : ℕ → Stream' α → List α

take n s returns a list of the n first elements of stream s

Equations

• Stream'.take 0 x = []
• Stream'.take (Nat.succ n) x = Stream'.head x :: Stream'.take n (Stream'.tail x)

def Stream'.cycleF {α : Type u_1} : α × List α × α × List α → α

An auxiliary definition for Stream'.cycle corecursive def

Equations

• Stream'.cycleF x = match x with | (v, fst, fst_1, snd) => v

def Stream'.cycleG {α : Type u_1} : α × List α × α × List α → α × List α × α × List α

An auxiliary definition for Stream'.cycle corecursive def

Equations

• Stream'.cycleG x = match x with | (fst, [], v₀, l₀) => (v₀, l₀, v₀, l₀) | (fst, v₂ :: l₂, v₀, l₀) => (v₂, l₂, v₀, l₀)

def Stream'.cycle {α : Type u_1} (l : List α) : l ≠ [] → Stream' α

Interpret a nonempty list as a cyclic stream.

Equations

• Stream'.cycle x✝ x = match x✝, x with | [], h => absurd ⋯ h | a :: l, x => Stream'.corec Stream'.cycleF Stream'.cycleG (a, l, a, l)

def Stream'.tails {α : Type u_1} (s : Stream' α) : Stream' (Stream' α)

Tails of a stream, starting with Stream'.tail s.

Equations

• Stream'.tails s = Stream'.corec id Stream'.tail (Stream'.tail s)

def Stream'.initsCore {α : Type u_1} (l : List α) (s : Stream' α) : Stream' (List α)

An auxiliary definition for Stream'.inits.

Equations

• One or more equations did not get rendered due to their size.

def Stream'.inits {α : Type u_1} (s : Stream' α) : Stream' (List α)

Nonempty initial segments of a stream.

Equations

• Stream'.inits s = Stream'.initsCore [Stream'.head s] (Stream'.tail s)

def Stream'.pure {α : Type u_1} (a : α) : Stream' α

A constant stream, same as Stream'.const.

Equations

• Stream'.pure a = Stream'.const a

def Stream'.apply {α : Type u_1} {β : Type u_2} (f : Stream' (α → β)) (s : Stream' α) : Stream' β

Given a stream of functions and a stream of values, apply n-th function to n-th value.

Equations

• (f ⊛ s) n = Stream'.get f n (Stream'.get s n)

def Stream'.«term_⊛_» : Lean.TrailingParserDescr

Equations

• Stream'.«term_⊛_» = Lean.ParserDescr.trailingNode `Stream'.term_⊛_ 75 75 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ⊛ ") (Lean.ParserDescr.cat `term 76))

def Stream'.nats : Stream' ℕ

The stream of natural numbers: Stream'.get n Stream'.nats = n.

Equations

• Stream'.nats n = n