blob: bcff54ee79fffbbe1abefb8b5d801bac3aa84635 [file]
/-
Copyright (c) 2025 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/
prelude
import Init.Data.Vector.Lemmas
import Init.Data.Vector.Attach
import Init.Data.Array.Monadic
import Init.Control.Lawful.Lemmas
/-!
# Lemmas about `Vector.forIn'` and `Vector.forIn`.
-/
set_option linter.listVariables true -- Enforce naming conventions for `List`/`Array`/`Vector` variables.
set_option linter.indexVariables true -- Enforce naming conventions for index variables.
namespace Vector
open Nat
/-! ## Monadic operations -/
@[simp] theorem map_toArray_inj [Monad m] [LawfulMonad m]
{xs : m (Vector α n)} {ys : m (Vector α n)} :
toArray <$> xs = toArray <$> ys ↔ xs = ys :=
_root_.map_inj_right (by simp)
/-! ### mapM -/
@[simp]
theorem mapM_pure [Monad m] [LawfulMonad m] {xs : Vector α n} (f : α → β) :
xs.mapM (m := m) (pure <| f ·) = pure (xs.map f) := by
apply map_toArray_inj.mp
simp
@[congr] theorem mapM_congr [Monad m] {xs ys : Vector α n} (w : xs = ys)
{f : α → m β} :
xs.mapM f = ys.mapM f := by
subst w
simp
@[simp] theorem mapM_mk_empty [Monad m] {f : α → m β} :
(mk #[] rfl).mapM f = pure #v[] := by
unfold mapM
unfold mapM.go
simp
@[simp] theorem mapM_append [Monad m] [LawfulMonad m]
{f : α → m β} {xs : Vector α n} {ys : Vector α n'} :
(xs ++ ys).mapM f = (return (← xs.mapM f) ++ (← ys.mapM f)) := by
apply map_toArray_inj.mp
suffices toArray <$> (xs ++ ys).mapM f = (return (← toArray <$> xs.mapM f) ++ (← toArray <$> ys.mapM f)) by
rw [this]
simp only [bind_pure_comp, Functor.map_map, bind_map_left, map_bind, toArray_append]
simp
/-! ### foldlM and foldrM -/
theorem foldlM_map [Monad m] {f : β₁ → β₂} {g : α → β₂ → m α} {xs : Vector β₁ n} {init : α} :
(xs.map f).foldlM g init = xs.foldlM (fun x y => g x (f y)) init := by
rcases xs with ⟨xs, rfl⟩
simp [Array.foldlM_map]
theorem foldrM_map [Monad m] [LawfulMonad m] {f : β₁ → β₂} {g : β₂ → α → m α} {xs : Vector β₁ n} {init : α} :
(xs.map f).foldrM g init = xs.foldrM (fun x y => g (f x) y) init := by
rcases xs with ⟨xs, rfl⟩
simp [Array.foldrM_map]
theorem foldlM_filterMap [Monad m] [LawfulMonad m] {f : α → Option β} {g : γ → β → m γ} {xs : Vector α n} {init : γ} :
(xs.filterMap f).foldlM g init =
xs.foldlM (fun x y => match f y with | some b => g x b | none => pure x) init := by
rcases xs with ⟨xs, rfl⟩
simp [Array.foldlM_filterMap]
rfl
theorem foldrM_filterMap [Monad m] [LawfulMonad m] {f : α → Option β} {g : β → γ → m γ} {xs : Vector α n} {init : γ} :
(xs.filterMap f).foldrM g init =
xs.foldrM (fun x y => match f x with | some b => g b y | none => pure y) init := by
rcases xs with ⟨xs, rfl⟩
simp [Array.foldrM_filterMap]
rfl
theorem foldlM_filter [Monad m] [LawfulMonad m] {p : α → Bool} {g : β → α → m β} {xs : Vector α n} {init : β} :
(xs.filter p).foldlM g init =
xs.foldlM (fun x y => if p y then g x y else pure x) init := by
rcases xs with ⟨xs, rfl⟩
simp [Array.foldlM_filter]
theorem foldrM_filter [Monad m] [LawfulMonad m] {p : α → Bool} {g : α → β → m β} {xs : Vector α n} {init : β} :
(xs.filter p).foldrM g init =
xs.foldrM (fun x y => if p x then g x y else pure y) init := by
rcases xs with ⟨xs, rfl⟩
simp [Array.foldrM_filter]
@[simp] theorem foldlM_attachWith [Monad m]
{xs : Vector α n} {q : α → Prop} (H : ∀ a, a ∈ xs → q a) {f : β → { x // q x} → m β} {b} :
(xs.attachWith q H).foldlM f b = xs.attach.foldlM (fun b ⟨a, h⟩ => f b ⟨a, H _ h⟩) b := by
rcases xs with ⟨xs, rfl⟩
simp [Array.foldlM_map]
@[simp] theorem foldrM_attachWith [Monad m] [LawfulMonad m]
{xs : Vector α n} {q : α → Prop} (H : ∀ a, a ∈ xs → q a) {f : { x // q x} → β → m β} {b} :
(xs.attachWith q H).foldrM f b = xs.attach.foldrM (fun a acc => f ⟨a.1, H _ a.2⟩ acc) b := by
rcases xs with ⟨xs, rfl⟩
simp [Array.foldrM_map]
/-! ### forM -/
@[congr] theorem forM_congr [Monad m] {as bs : Vector α n} (w : as = bs)
{f : α → m PUnit} :
forM as f = forM bs f := by
cases as <;> cases bs
simp_all
@[simp] theorem forM_append [Monad m] [LawfulMonad m] {xs : Vector α n} {ys : Vector α n'} {f : α → m PUnit} :
forM (xs ++ ys) f = (do forM xs f; forM ys f) := by
rcases xs with ⟨xs, rfl⟩
rcases ys with ⟨ys, rfl⟩
simp
@[simp] theorem forM_map [Monad m] [LawfulMonad m] {xs : Vector α n} {g : α → β} {f : β → m PUnit} :
forM (xs.map g) f = forM xs (fun a => f (g a)) := by
rcases xs with ⟨xs, rfl⟩
simp
/-! ### forIn' -/
@[congr] theorem forIn'_congr [Monad m] {xs ys : Vector α n} (w : xs = ys)
{b b' : β} (hb : b = b')
{f : (a' : α) → a' ∈ xs → β → m (ForInStep β)}
{g : (a' : α) → a' ∈ ys → β → m (ForInStep β)}
(h : ∀ a m b, f a (by simpa [w] using m) b = g a m b) :
forIn' xs b f = forIn' ys b' g := by
cases xs <;> cases ys
simp only [eq_mk, mem_mk, forIn'_mk] at w h ⊢
exact Array.forIn'_congr w hb h
/--
We can express a for loop over a vector as a fold,
in which whenever we reach `.done b` we keep that value through the rest of the fold.
-/
theorem forIn'_eq_foldlM [Monad m] [LawfulMonad m]
{xs : Vector α n} (f : (a : α) → a ∈ xs → β → m (ForInStep β)) (init : β) :
forIn' xs init f = ForInStep.value <$>
xs.attach.foldlM (fun b ⟨a, m⟩ => match b with
| .yield b => f a m b
| .done b => pure (.done b)) (ForInStep.yield init) := by
rcases xs with ⟨xs, rfl⟩
simp [Array.forIn'_eq_foldlM]
rfl
/-- We can express a for loop over a vector which always yields as a fold. -/
@[simp] theorem forIn'_yield_eq_foldlM [Monad m] [LawfulMonad m]
{xs : Vector α n} (f : (a : α) → a ∈ xs → β → m γ) (g : (a : α) → a ∈ xs → β → γ → β) (init : β) :
forIn' xs init (fun a m b => (fun c => .yield (g a m b c)) <$> f a m b) =
xs.attach.foldlM (fun b ⟨a, m⟩ => g a m b <$> f a m b) init := by
rcases xs with ⟨xs, rfl⟩
simp
@[simp] theorem forIn'_pure_yield_eq_foldl [Monad m] [LawfulMonad m]
{xs : Vector α n} (f : (a : α) → a ∈ xs → β → β) (init : β) :
forIn' xs init (fun a m b => pure (.yield (f a m b))) =
pure (f := m) (xs.attach.foldl (fun b ⟨a, h⟩ => f a h b) init) := by
rcases xs with ⟨xs, rfl⟩
simp [Array.forIn'_pure_yield_eq_foldl, Array.foldl_map]
@[simp] theorem forIn'_yield_eq_foldl
{xs : Vector α n} (f : (a : α) → a ∈ xs → β → β) (init : β) :
forIn' (m := Id) xs init (fun a m b => .yield (f a m b)) =
xs.attach.foldl (fun b ⟨a, h⟩ => f a h b) init := by
rcases xs with ⟨xs, rfl⟩
simp [List.foldl_map]
@[simp] theorem forIn'_map [Monad m] [LawfulMonad m]
{xs : Vector α n} (g : α → β) (f : (b : β) → b ∈ xs.map g → γ → m (ForInStep γ)) :
forIn' (xs.map g) init f = forIn' xs init fun a h y => f (g a) (mem_map_of_mem h) y := by
rcases xs with ⟨xs, rfl⟩
simp
/--
We can express a for loop over a vector as a fold,
in which whenever we reach `.done b` we keep that value through the rest of the fold.
-/
theorem forIn_eq_foldlM [Monad m] [LawfulMonad m]
{xs : Vector α n} (f : α → β → m (ForInStep β)) (init : β) :
forIn xs init f = ForInStep.value <$>
xs.foldlM (fun b a => match b with
| .yield b => f a b
| .done b => pure (.done b)) (ForInStep.yield init) := by
rcases xs with ⟨xs, rfl⟩
simp [Array.forIn_eq_foldlM]
rfl
/-- We can express a for loop over a vector which always yields as a fold. -/
@[simp] theorem forIn_yield_eq_foldlM [Monad m] [LawfulMonad m]
{xs : Vector α n} (f : α → β → m γ) (g : α → β → γ → β) (init : β) :
forIn xs init (fun a b => (fun c => .yield (g a b c)) <$> f a b) =
xs.foldlM (fun b a => g a b <$> f a b) init := by
rcases xs with ⟨xs, rfl⟩
simp
@[simp] theorem forIn_pure_yield_eq_foldl [Monad m] [LawfulMonad m]
{xs : Vector α n} (f : α → β → β) (init : β) :
forIn xs init (fun a b => pure (.yield (f a b))) =
pure (f := m) (xs.foldl (fun b a => f a b) init) := by
rcases xs with ⟨xs, rfl⟩
simp [Array.forIn_pure_yield_eq_foldl, Array.foldl_map]
@[simp] theorem forIn_yield_eq_foldl
{xs : Vector α n} (f : α → β → β) (init : β) :
forIn (m := Id) xs init (fun a b => .yield (f a b)) =
xs.foldl (fun b a => f a b) init := by
rcases xs with ⟨xs, rfl⟩
simp
@[simp] theorem forIn_map [Monad m] [LawfulMonad m]
{xs : Vector α n} (g : α → β) (f : β → γ → m (ForInStep γ)) :
forIn (xs.map g) init f = forIn xs init fun a y => f (g a) y := by
rcases xs with ⟨xs, rfl⟩
simp
/-! ### allM and anyM -/
@[simp] theorem anyM_pure [Monad m] [LawfulMonad m] {p : α → Bool} {xs : Vector α n} :
xs.anyM (m := m) (pure <| p ·) = pure (xs.any p) := by
cases xs
simp
@[simp] theorem allM_pure [Monad m] [LawfulMonad m] {p : α → Bool} {xs : Vector α n} :
xs.allM (m := m) (pure <| p ·) = pure (xs.all p) := by
cases xs
simp
/-! ### findM? and findSomeM? -/
theorem findM?_pure {m} [Monad m] [LawfulMonad m] {p : α → Bool} {xs : Vector α n} :
findM? (m := m) (pure <| p ·) xs = pure (xs.find? p) := by
cases xs
simp
@[simp]
theorem findSomeM?_pure [Monad m] [LawfulMonad m] {f : α → Option β} {xs : Vector α n} :
findSomeM? (m := m) (pure <| f ·) xs = pure (xs.findSome? f) := by
cases xs
simp
end Vector