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} (a : α) (s : Stream' α) : Stream' α

Prepend an element to a stream.

Equations

• Stream'.cons a s 0 = a
• Stream'.cons a s n.succ = s n

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

Prepend an element to a stream.

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} (s : Stream' α) (n : ℕ) : α

Get the n-th element of a stream.

Equations

• s.get n = s n

@[reducible, inline]

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

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

Equations

• s.head = s.get 0

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

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

Equations

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

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

Drop first n elements of a stream.

Equations

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

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

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

Equations

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

def Stream'.Any {α : Type u} (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 (s.get n)

instance Stream'.instMembership {α : Type u} : Membership α (Stream' α)

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

Equations

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

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

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

Equations

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

def Stream'.zip {α : Type u} {β : Type v} {δ : Type w} (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 (s₁.get n) (s₂.get n)

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

Enumerate a stream by tagging each element with its index.

Equations

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

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

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

Equations

• Stream'.const a x✝ = a

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

Iterates of a function as a stream.

Equations

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

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

Given functions f : α → β and g : α → α, corec f g creates a stream by:

1. Starting with an initial value a : α
2. Applying g repeatedly to get a stream of α values
3. Applying f to each value to convert them to β

Equations

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

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

Given an initial value a : α and functions f : α → β and g : α → α, corecOn a f g creates a stream by repeatedly:

1. Applying f to the current value to get the next stream element
2. Applying g to get the next value to process This is equivalent to corec f g a.

Equations

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

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

Given a function f : α → β × α, corec' f creates a stream by repeatedly:

1. Starting with an initial value a : α
2. Applying f to get both the next stream element (β) and next state value (α) This is a more convenient form when the next element and state are computed together.

Equations

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

def Stream'.corecState {σ α : 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)

@[reducible, inline]

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

Equations

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

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

Interleave two streams.

Equations

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

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

Interleave two streams.

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} (s : Stream' α) : Stream' α

Elements of a stream with even indices.

Equations

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

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

Elements of a stream with odd indices.

Equations

• s.odd = s.tail.even

def Stream'.appendStream' {α : Type u} : 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

Append a stream to a list.

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} : ℕ → Stream' α → List α

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

Equations

• Stream'.take 0 x✝ = []
• Stream'.take n.succ x✝ = x✝.head :: Stream'.take n x✝.tail

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

An auxiliary definition for Stream'.cycle corecursive def

Equations

• Stream'.cycleF (v, fst, fst_1, snd) = v

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

An auxiliary definition for Stream'.cycle corecursive def

Equations

• Stream'.cycleG (fst, [], v₀, l₀) = (v₀, l₀, v₀, l₀)
• Stream'.cycleG (fst, v₂ :: l₂, v₀, l₀) = (v₂, l₂, v₀, l₀)

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

Interpret a nonempty list as a cyclic stream.

Equations

• Stream'.cycle [] h = absurd ⋯ h
• Stream'.cycle (a :: l) x_2 = Stream'.corec Stream'.cycleF Stream'.cycleG (a, l, a, l)

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

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

Equations

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

def Stream'.initsCore {α : Type u} (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} (s : Stream' α) : Stream' (List α)

Nonempty initial segments of a stream.

Equations

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

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

A constant stream, same as Stream'.const.

Equations

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

def Stream'.apply {α : Type u} {β : Type v} (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 = f.get n (s.get n)

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

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

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