Lemmas about List.mapM and List.forM.

Monadic operations

mapM

def List.mapM' {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] (f : α → m β) : List α → m (List β)

Alternate (non-tail-recursive) form of mapM for proofs.

Equations

• List.mapM' f [] = pure []
• List.mapM' f (a :: l) = do let __do_lift ← f a let __do_lift_1 ← List.mapM' f l pure (__do_lift :: __do_lift_1)

@[simp]

theorem List.mapM'_nil {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] {f : α → m β} : List.mapM' f [] = pure []

@[simp]

theorem List.mapM'_cons {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} {a : α} {l : List α} [Monad m] {f : α → m β} : List.mapM' f (a :: l) = do let __do_lift ← f a let __do_lift_1 ← List.mapM' f l pure (__do_lift :: __do_lift_1)

theorem List.mapM'_eq_mapM {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] [LawfulMonad m] (f : α → m β) (l : List α) : List.mapM' f l = List.mapM f l

theorem List.mapM'_eq_mapM.go {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] [LawfulMonad m] (f : α → m β) (l : List α) (acc : List β) : List.mapM.loop f l acc = do let __do_lift ← List.mapM' f l pure (acc.reverse ++ __do_lift)

@[simp]

theorem List.mapM_nil {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] (f : α → m β) : List.mapM f [] = pure []

@[simp]

theorem List.mapM_cons {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} {a : α} {l : List α} [Monad m] [LawfulMonad m] (f : α → m β) : List.mapM f (a :: l) = do let __do_lift ← f a let __do_lift_1 ← List.mapM f l pure (__do_lift :: __do_lift_1)

@[simp]

theorem List.mapM_append {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] [LawfulMonad m] (f : α → m β) {l₁ : List α} {l₂ : List α} : List.mapM f (l₁ ++ l₂) = do let __do_lift ← List.mapM f l₁ let __do_lift_1 ← List.mapM f l₂ pure (__do_lift ++ __do_lift_1)

theorem List.foldlM_cons_eq_append {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] [LawfulMonad m] (f : α → m β) (as : List α) (b : β) (bs : List β) : List.foldlM (fun (acc : List β) (a : α) => do let __do_lift ← f a pure (__do_lift :: acc)) (b :: bs) as = (fun (x : List β) => x ++ b :: bs) <$> List.foldlM (fun (acc : List β) (a : α) => do let __do_lift ← f a pure (__do_lift :: acc)) [] as

Auxiliary lemma for mapM_eq_reverse_foldlM_cons.

theorem List.mapM_eq_reverse_foldlM_cons {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] [LawfulMonad m] (f : α → m β) (l : List α) : List.mapM f l = List.reverse <$> List.foldlM (fun (acc : List β) (a : α) => do let __do_lift ← f a pure (__do_lift :: acc)) [] l

forM

@[simp]

theorem List.forM_nil' {m : Type u_1 → Type u_2} {α : Type u_3} {f : α → m PUnit} [Monad m] : [].forM f = pure PUnit.unit

@[simp]

theorem List.forM_cons' {m : Type u_1 → Type u_2} : ∀ {α : Type u_3} {a : α} {as : List α} {f : α → m PUnit} [inst : Monad m], (a :: as).forM f = do f a as.forM f

@[simp]

theorem List.forM_append {m : Type u_1 → Type u_2} {α : Type u_3} [Monad m] [LawfulMonad m] (l₁ : List α) (l₂ : List α) (f : α → m PUnit) : (l₁ ++ l₂).forM f = do l₁.forM f l₂.forM f

allM

theorem List.allM_eq_not_anyM_not {m : Type → Type u_1} {α : Type u_2} [Monad m] [LawfulMonad m] (p : α → m Bool) (as : List α) : List.allM p as = (fun (x : Bool) => !x) <$> List.anyM (fun (x : α) => (fun (x : Bool) => !x) <$> p x) as

foldlM and foldrM

theorem List.foldlM_map {m : Type u_1 → Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} {α : Type u_1} [Monad m] (f : β₁ → β₂) (g : α → β₂ → m α) (l : List β₁) (init : α) : List.foldlM g init (List.map f l) = List.foldlM (fun (x : α) (y : β₁) => g x (f y)) init l

theorem List.foldrM_map {m : Type u_1 → Type u_2} {β₁ : Type u_3} {β₂ : Type u_4} {α : Type u_1} [Monad m] [LawfulMonad m] (f : β₁ → β₂) (g : β₂ → α → m α) (l : List β₁) (init : α) : List.foldrM g init (List.map f l) = List.foldrM (fun (x : β₁) (y : α) => g (f x) y) init l