Documentation

ToCslib.Control.Loop.Basic

Effect-free loops as folds #

Id.run do code elaborates its for loops to forIn over the iterated container, with the mutable variables as the loop state. This module relates such loops to folds over lists, so that imperative code can be compared with a functional specification by rewriting.

The loop_norm simp set collects these rewrites with core's and the monad laws that expose a yield-only body; simp only [loop_norm] turns most Id.run do loops with yield-only bodies into List.foldl.

Legacy ranges as lists #

theorem Std.Legacy.Range.size_mk_one (a b : Nat) (h : 0 < 1) :
[a:b].size = b - a

A range with unit step has stop - start elements.

@[simp]
theorem Std.Legacy.Range.mem_mk_one_iff {a b i : Nat} (h : 0 < 1) :
i ∈ [a:b] ↔ a ≤ i ∧ i < b

Membership in a range with unit step.

theorem Std.Legacy.Range.mem_of_mem_range'_sub {a b i : Nat} (h : i ∈ List.range' a (b - a)) :
i ∈ [a:b]
theorem Std.Legacy.Range.forIn_eq_forIn_range'_sub {m : Type u → Type v} {β : Type u} [Monad m] (a b : Nat) (init : β) (f : Nat → β → m (ForInStep β)) :
forIn [a:b] init f = forIn (List.range' a (b - a)) init f

A for loop over [a:b] is the loop over List.range' a (b - a).

theorem Std.Legacy.Range.forIn_eq_forIn_range {m : Type u → Type v} {β : Type u} [Monad m] (n : Nat) (init : β) (f : Nat → β → m (ForInStep β)) :
forIn [:n] init f = forIn (List.range n) init f

A for loop over [0:n] is the loop over List.range n.

theorem Std.Legacy.Range.forIn'_eq_forIn'_range'_sub {m : Type u → Type v} {β : Type u} [Monad m] (a b : Nat) (init : β) (f : (i : Nat) → i ∈ [a:b] → β → m (ForInStep β)) :
forIn' [a:b] init f = forIn' (List.range' a (b - a)) init fun (i : Nat) (h : i ∈ List.range' a (b - a)) (acc : β) => f i ⋯ acc

The forIn' twin of forIn_eq_forIn_range'_sub.

theorem Std.Legacy.Range.forIn'_eq_forIn'_range {m : Type u → Type v} {β : Type u} [Monad m] (n : Nat) (init : β) (f : (i : Nat) → i ∈ [:n] → β → m (ForInStep β)) :
forIn' [:n] init f = forIn' (List.range n) init fun (i : Nat) (h : i ∈ List.range n) (acc : β) => f i ⋯ acc

The forIn' twin of forIn_eq_forIn_range.

Bodies that only yield #

theorem List.forIn_eq_pure_foldl {m : Type u → Type v} {α : Type u₁} {β : Type u} [Monad m] [LawfulMonad m] {xs : List α} {init : β} {f : α → β → m (ForInStep β)} (g : β → α → β) (h : ∀ (a : α), a ∈ xs → ∀ (b : β), f a b = pure (ForInStep.yield (g b a))) :
forIn xs init f = pure (foldl g init xs)

A loop whose body yields g b a on every element a of the list is the left fold of g.

theorem List.idRun_forIn_eq_foldl {α : Type u₁} {β : Type u} {xs : List α} {init : β} {f : α → β → Id (ForInStep β)} (g : β → α → β) (h : ∀ (a : α), a ∈ xs → ∀ (b : β), f a b = pure (ForInStep.yield (g b a))) :
(forIn xs init f).run = foldl g init xs

forIn_eq_pure_foldl read through Id.run.

theorem List.forIn'_eq_pure_foldl {m : Type u → Type v} {α : Type u₁} {β : Type u} [Monad m] [LawfulMonad m] {xs : List α} {init : β} {f : (a : α) → a ∈ xs → β → m (ForInStep β)} (g : β → α → β) (h : ∀ (a : α) (ha : a ∈ xs) (b : β), f a ha b = pure (ForInStep.yield (g b a))) :
forIn' xs init f = pure (foldl g init xs)

The forIn' twin of forIn_eq_pure_foldl, for a body that does not use the membership proof in its result.

theorem List.idRun_forIn'_eq_foldl {α : Type u₁} {β : Type u} {xs : List α} {init : β} {f : (a : α) → a ∈ xs → β → Id (ForInStep β)} (g : β → α → β) (h : ∀ (a : α) (ha : a ∈ xs) (b : β), f a ha b = pure (ForInStep.yield (g b a))) :
(forIn' xs init f).run = foldl g init xs

forIn'_eq_pure_foldl read through Id.run.

Congruence #

theorem List.forIn_congr {m : Type u → Type v} {α : Type u₁} {β : Type u} [Monad m] {xs : List α} {init : β} {f g : α → β → m (ForInStep β)} (h : ∀ (a : α), a ∈ xs → ∀ (b : β), f a b = g a b) :
forIn xs init f = forIn xs init g

Two loops over a list agree when their bodies agree on its elements.

Concatenation #

theorem List.forIn_append {m : Type u → Type v} {α : Type u₁} {β : Type u} [Monad m] [LawfulMonad m] (xs ys : List α) (init : β) (f : α → β → m (ForInStep β)) :
forIn (xs ++ ys) init f = do let r ← foldlM (fun (r : ForInStep β) (a : α) => match r with | ForInStep.yield b => f a b | ForInStep.done b => pure (ForInStep.done b)) (ForInStep.yield init) xs match r with | ForInStep.yield b => forIn ys b f | ForInStep.done b => pure b

A loop over xs ++ ys runs the loop over xs, as the fold of List.forIn_eq_foldlM, and continues over ys unless that fold stopped.

theorem List.forIn_append_of_yield {m : Type u → Type v} {α : Type u₁} {β : Type u} [Monad m] [LawfulMonad m] (xs ys : List α) (init : β) {f : α → β → m (ForInStep β)} (g : α → β → m β) (h : ∀ (a : α), a ∈ xs → ∀ (b : β), f a b = ForInStep.yield <$> g a b) :
forIn (xs ++ ys) init f = do let b ← forIn xs init f forIn ys b f

When the body only yields on xs, a loop over xs ++ ys is the loop over ys started from the state the loop over xs returns.

Folds through a sequence of states #

theorem List.foldl_eq_of_trace {α : Type u₁} {γ : Type w} (step : γ → α → γ) (S : Nat → γ) (xs : List α) (h : ∀ (i : Nat) (hi : i < xs.length), step (S i) xs[i] = S (i + 1)) :
foldl step (S 0) xs = S xs.length

A left fold whose i-th step takes the state S i to S (i + 1) ends in S xs.length.

theorem List.foldl_range'_eq_of_trace {γ : Type w} (step : γ → Nat → γ) (S : Nat → γ) (s n k : Nat) (h : ∀ (i : Nat), i < n → step (S i) (s + k * i) = S (i + 1)) :
foldl step (S 0) (range' s n k) = S n

A left fold over List.range' s n k whose step at s + k * i takes S i to S (i + 1) ends in S n.

theorem List.fst_foldl {α : Type u₁} {γ : Type w} {δ : Type v} (F : γ × δ → α → γ × δ) (xs : List α) (p : γ × δ) (h : ∀ (q : γ × δ) (a : α), (F q a).fst = (F (q.fst, p.snd) a).fst) :
(foldl F p xs).fst = foldl (fun (c : γ) (a : α) => (F (c, p.snd) a).fst) p.fst xs

The first component of a left fold over pairs, when the first component of each step does not depend on the second component of the state, is the fold of the first components.

theorem List.snd_foldl {α : Type u₁} {γ : Type w} {δ : Type v} (F : γ × δ → α → γ × δ) (xs : List α) (p : γ × δ) (h : ∀ (q : γ × δ) (a : α), (F q a).snd = (F (p.fst, q.snd) a).snd) :
(foldl F p xs).snd = foldl (fun (c : δ) (a : α) => (F (p.fst, c) a).snd) p.snd xs

The second component of a left fold over pairs, when the second component of each step does not depend on the first component of the state, is the fold of the second components.

theorem List.eq_add_mul_length_of_range'_eq_append_cons {s n step cur : Nat} {pref suff : List Nat} (h : range' s n step = pref ++ cur :: suff) :
cur = s + step * pref.length

The element at position pref.length of List.range' s n step is s + step * pref.length, as the verification conditions of a loop over a range need.

theorem List.length_lt_of_range'_eq_append_cons {s n step cur : Nat} {pref suff : List Nat} (h : range' s n step = pref ++ cur :: suff) :
pref.length < n

A decomposition List.range' s n step = pref ++ cur :: suff has pref.length < n.

theorem Std.Legacy.Range.forIn_eq_pure_foldl {m : Type u → Type v} {β : Type u} [Monad m] [LawfulMonad m] {a b : Nat} {init : β} {f : Nat → β → m (ForInStep β)} (g : β → Nat → β) (h : ∀ (i : Nat), a ≤ i → i < b → ∀ (acc : β), f i acc = pure (ForInStep.yield (g acc i))) :
forIn [a:b] init f = pure (List.foldl g init (List.range' a (b - a)))

A loop over [a:b] whose body yields g acc i at every index a ≤ i < b is the left fold of g over List.range' a (b - a).

theorem Std.Legacy.Range.idRun_forIn_eq_foldl {β : Type u} {a b : Nat} {init : β} {f : Nat → β → Id (ForInStep β)} (g : β → Nat → β) (h : ∀ (i : Nat), a ≤ i → i < b → ∀ (acc : β), f i acc = pure (ForInStep.yield (g acc i))) :
(forIn [a:b] init f).run = List.foldl g init (List.range' a (b - a))

forIn_eq_pure_foldl read through Id.run.

theorem Std.Legacy.Range.forIn_congr {m : Type u → Type v} {β : Type u} [Monad m] {r : Range} {init : β} {f g : Nat → β → m (ForInStep β)} (h : ∀ (i : Nat), i ∈ r → ∀ (acc : β), f i acc = g i acc) :
forIn r init f = forIn r init g

Two loops over a range agree when their bodies agree on its members.

Containers iterating over a list #

theorem Std.Internal.forIn_eq_pure_foldl_toList {m : Type u → Type v} {α : Type u₁} {β : Type u} {ρ : Type w} [Monad m] [LawfulMonad m] [ForIn m ρ α] [ForIn Id ρ α] [PureForIn m ρ α] (xs : ρ) {init : β} {f : α → β → m (ForInStep β)} (g : β → α → β) (h : ∀ (a : α), a ∈ ForIn.toList xs → ∀ (b : β), f a b = pure (ForInStep.yield (g b a))) :
forIn xs init f = pure (List.foldl g init (ForIn.toList xs))

List.forIn_eq_pure_foldl for every container whose loop is the loop over ForIn.toList.

theorem Std.Internal.idRun_forIn_eq_foldl_toList {α : Type u₁} {β : Type u} {ρ : Type w} [ForIn Id ρ α] [ForIn Id ρ α] [PureForIn Id ρ α] (xs : ρ) {init : β} {f : α → β → Id (ForInStep β)} (g : β → α → β) (h : ∀ (a : α), a ∈ ForIn.toList xs → ∀ (b : β), f a b = pure (ForInStep.yield (g b a))) :
(forIn xs init f).run = List.foldl g init (ForIn.toList xs)

forIn_eq_pure_foldl_toList read through Id.run.

theorem Std.Internal.forIn'_eq_pure_foldl_toList {m : Type u → Type v} {α : Type u₁} {β : Type u} {ρ : Type w} [Monad m] [LawfulMonad m] {d : Membership α ρ} [ForIn' m ρ α d] [ForIn Id ρ α] [LawfulMemForInId ρ α] [PureForIn' m ρ α] (xs : ρ) {init : β} {f : (a : α) → a ∈ xs → β → m (ForInStep β)} (g : β → α → β) (h : ∀ (a : α) (ha : a ∈ xs) (b : β), f a ha b = pure (ForInStep.yield (g b a))) :
forIn' xs init f = pure (List.foldl g init (ForIn.toList xs))

The forIn' twin of forIn_eq_pure_foldl_toList, for a body that does not use the membership proof in its result.

theorem Std.Internal.forIn_congr_toList {m : Type u → Type v} {α : Type u₁} {β : Type u} {ρ : Type w} [Monad m] [ForIn m ρ α] [ForIn Id ρ α] [PureForIn m ρ α] (xs : ρ) {init : β} {f g : α → β → m (ForInStep β)} (h : ∀ (a : α), a ∈ ForIn.toList xs → ∀ (b : β), f a b = g a b) :
forIn xs init f = forIn xs init g

Two loops over a container that iterates over ForIn.toList agree when their bodies agree on its elements.

Normalization #

theorem ite_pure_yield {m : Type u → Type v} {β : Type u} [Pure m] (c : Prop) [Decidable c] (x y : β) :

Both branches of an if that yield, as one yield of the if.

theorem dite_pure_yield {m : Type u → Type v} {β : Type u} [Pure m] (c : Prop) [Decidable c] (x : c → β) (y : ¬c → β) :
(if h : c then pure (ForInStep.yield (x h)) else pure (ForInStep.yield (y h))) = pure (ForInStep.yield (if h : c then x h else y h))

The dependent twin of ite_pure_yield.