Theorem: LeanColls.Fold.any_eq_any_toList (LeanColls/Classes/Ops/Fold.lean)

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
⊢ any f c = (toList c).any f
Tactic:
unfold any
State after:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
⊢ (match foldM c (fun x x => if f x = true then Except.error () else Except.ok ()) () with
    | Except.ok PUnit.unit => false
    | Except.error PUnit.unit => true) =
    (toList c).any f

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
⊢ (match foldM c (fun x x => if f x = true then Except.error () else Except.ok ()) () with
    | Except.ok PUnit.unit => false
    | Except.error PUnit.unit => true) =
    (toList c).any f
Tactic:
generalize hf' : (fun _ _ => _) = f'
State after:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
⊢ (match foldM c f' () with
    | Except.ok PUnit.unit => false
    | Except.error PUnit.unit => true) =
    (toList c).any f

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
⊢ foldM c f' () = Except.error () ↔ (toList c).any f = true
Tactic:
rw [ToList.foldM_eq_fold]
State after:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
⊢ fold c
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) =
      Except.error () ↔
    (toList c).any f = true

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
⊢ fold c
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) =
      Except.error () ↔
    (toList c).any f = true
Tactic:
have ⟨L,perm,h⟩ := ToList.fold_eq_fold_toList c
State after:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
L : List τ
perm : L.Perm (toList c)
h : ∀ {β : Type} (f : β → τ → β) (init : β), fold c f init = List.foldl f init L
⊢ fold c
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) =
      Except.error () ↔
    (toList c).any f = true

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
L : List τ
perm : L.Perm (toList c)
h : ∀ {β : Type} (f : β → τ → β) (init : β), fold c f init = List.foldl f init L
⊢ fold c
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) =
      Except.error () ↔
    (toList c).any f = true
Tactic:
rw [h]
State after:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
L : List τ
perm : L.Perm (toList c)
h : ∀ {β : Type} (f : β → τ → β) (init : β), fold c f init = List.foldl f init L
⊢ List.foldl
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) L =
      Except.error () ↔
    (toList c).any f = true

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
L : List τ
perm : L.Perm (toList c)
h : ∀ {β : Type} (f : β → τ → β) (init : β), fold c f init = List.foldl f init L
⊢ List.foldl
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) L =
      Except.error () ↔
    (toList c).any f = true
Tactic:
clear h
State after:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
L : List τ
perm : L.Perm (toList c)
⊢ List.foldl
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) L =
      Except.error () ↔
    (toList c).any f = true

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
L : List τ
perm : L.Perm (toList c)
⊢ List.foldl
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) L =
      Except.error () ↔
    (toList c).any f = true
Tactic:
simp_rw [List.any_eq_true, ← perm.mem_iff]
State after:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
L : List τ
perm : L.Perm (toList c)
⊢ List.foldl
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) L =
      Except.error () ↔
    ∃ x ∈ L, f x = true

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
L : List τ
perm : L.Perm (toList c)
⊢ List.foldl
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) L =
      Except.error () ↔
    ∃ x ∈ L, f x = true
Tactic:
clear perm c
State after:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
L : List τ
⊢ List.foldl
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) L =
      Except.error () ↔
    ∃ x ∈ L, f x = true

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
L : List τ
⊢ List.foldl
        (fun acc x => do
          let x_1 ← acc
          f' x_1 x)
        (pure ()) L =
      Except.error () ↔
    ∃ x ∈ L, f x = true
Tactic:
subst hf'
State after:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
L : List τ
⊢ List.foldl
        (fun acc x => do
          let x_1 ← acc
          (fun x x => if f x = true then Except.error () else Except.ok ()) x_1 x)
        (pure ()) L =
      Except.error () ↔
    ∃ x ∈ L, f x = true

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
L : List τ
⊢ List.foldl
        (fun acc x => do
          let x_1 ← acc
          (fun x x => if f x = true then Except.error () else Except.ok ()) x_1 x)
        (pure ()) L =
      Except.error () ↔
    ∃ x ∈ L, f x = true
Tactic:
rw [← List.foldlM_eq_foldl]
State after:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
L : List τ
⊢ List.foldlM (fun x x_1 => (fun x x => if f x = true then Except.error () else Except.ok ()) x x_1) () L =
      Except.error () ↔
    ∃ x ∈ L, f x = true

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
L : List τ
⊢ List.foldlM (fun x x_1 => (fun x x => if f x = true then Except.error () else Except.ok ()) x x_1) () L =
      Except.error () ↔
    ∃ x ∈ L, f x = true
Tactic:
induction L with
| nil => simp_all [pure, Except.pure]
| cons hd tl ih =>
  simp [bind, Except.bind]
  by_cases f hd = true <;> simp_all
State after:
no goals

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
this : foldM c f' () = Except.error () ↔ (toList c).any f = true
⊢ (match foldM c f' () with
    | Except.ok PUnit.unit => false
    | Except.error PUnit.unit => true) =
    (toList c).any f
Tactic:
rw [eq_comm]
State after:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
this : foldM c f' () = Except.error () ↔ (toList c).any f = true
⊢ (toList c).any f =
    match foldM c f' () with
    | Except.ok PUnit.unit => false
    | Except.error PUnit.unit => true

State before:
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
this : foldM c f' () = Except.error () ↔ (toList c).any f = true
⊢ (toList c).any f =
    match foldM c f' () with
    | Except.ok PUnit.unit => false
    | Except.error PUnit.unit => true
Tactic:
split
State after:
case h_1
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
this : foldM c f' () = Except.error () ↔ (toList c).any f = true
x✝ : Except Unit Unit
heq✝ : foldM c f' () = Except.ok PUnit.unit
⊢ (toList c).any f = false

case h_2
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
this : foldM c f' () = Except.error () ↔ (toList c).any f = true
x✝ : Except Unit Unit
heq✝ : foldM c f' () = Except.error PUnit.unit
⊢ (toList c).any f = true

State before:
case h_1
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
this : foldM c f' () = Except.error () ↔ (toList c).any f = true
x✝ : Except Unit Unit
heq✝ : foldM c f' () = Except.ok PUnit.unit
⊢ (toList c).any f = false
Tactic:
rw [Bool.eq_false_iff]
State after:
case h_1
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
this : foldM c f' () = Except.error () ↔ (toList c).any f = true
x✝ : Except Unit Unit
heq✝ : foldM c f' () = Except.ok PUnit.unit
⊢ (toList c).any f ≠ true

State before:
case h_1
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
this : foldM c f' () = Except.error () ↔ (toList c).any f = true
x✝ : Except Unit Unit
heq✝ : foldM c f' () = Except.ok PUnit.unit
⊢ (toList c).any f ≠ true
Tactic:
aesop
State after:
no goals

State before:
case h_2
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
c : C
f' : Unit → τ → Except Unit Unit
hf' : (fun x x => if f x = true then Except.error () else Except.ok ()) = f'
this : foldM c f' () = Except.error () ↔ (toList c).any f = true
x✝ : Except Unit Unit
heq✝ : foldM c f' () = Except.error PUnit.unit
⊢ (toList c).any f = true
Tactic:
aesop
State after:
no goals

State before:
case nil
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
⊢ List.foldlM (fun x x_1 => (fun x x => if f x = true then Except.error () else Except.ok ()) x x_1) () [] =
      Except.error () ↔
    ∃ x ∈ [], f x = true
Tactic:
simp_all [pure, Except.pure]
State after:
no goals

State before:
case cons
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
hd : τ
tl : List τ
ih :
  List.foldlM (fun x x_1 => (fun x x => if f x = true then Except.error () else Except.ok ()) x x_1) () tl =
      Except.error () ↔
    ∃ x ∈ tl, f x = true
⊢ List.foldlM (fun x x_1 => (fun x x => if f x = true then Except.error () else Except.ok ()) x x_1) () (hd :: tl) =
      Except.error () ↔
    ∃ x ∈ hd :: tl, f x = true
Tactic:
simp [bind, Except.bind]
State after:
case cons
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
hd : τ
tl : List τ
ih :
  List.foldlM (fun x x_1 => (fun x x => if f x = true then Except.error () else Except.ok ()) x x_1) () tl =
      Except.error () ↔
    ∃ x ∈ tl, f x = true
⊢ (match if f hd = true then Except.error () else Except.ok () with
      | Except.error err => Except.error err
      | Except.ok v => List.foldlM (fun x x => if f x = true then Except.error () else Except.ok ()) v tl) =
      Except.error () ↔
    f hd = true ∨ ∃ a ∈ tl, f a = true

State before:
case cons
C : Type u_1
τ : Type u_2
inst✝⁴ : Fold C τ
inst✝³ : LeanColls.ToList C τ
inst✝² : ToList C τ
inst✝¹ : LeanColls.ToList C τ
inst✝ : ToList C τ
f : τ → Bool
hd : τ
tl : List τ
ih :
  List.foldlM (fun x x_1 => (fun x x => if f x = true then Except.error () else Except.ok ()) x x_1) () tl =
      Except.error () ↔
    ∃ x ∈ tl, f x = true
⊢ (match if f hd = true then Except.error () else Except.ok () with
      | Except.error err => Except.error err
      | Except.ok v => List.foldlM (fun x x => if f x = true then Except.error () else Except.ok ()) v tl) =
      Except.error () ↔
    f hd = true ∨ ∃ a ∈ tl, f a = true
Tactic:
by_cases f hd = true <;> simp_all
State after:
no goals