algebra.big_operators.norm_num | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

70fd9563

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

2fe465de

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -160,7 +160,7 @@ theorem Multiset.cons_congr {α : Type _} (x : α) {xs : Multiset α} {xs' : Lis
 
 theorem Multiset.map_congr {α β : Type _} (f : α → β) {xs : Multiset α} {xs' : List α} {ys : List β}
     (xs_eq : xs = (xs' : Multiset α)) (ys_eq : xs'.map f = ys) : xs.map f = (ys : Multiset β) := by
-  rw [← ys_eq, ← Multiset.coe_map, xs_eq]
+  rw [← ys_eq, ← Multiset.map_coe, xs_eq]
 #align tactic.norm_num.multiset.map_congr Tactic.NormNum.Multiset.map_congr
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
@@ -426,7 +426,7 @@ theorem List.prod_congr {α : Type _} [Monoid α] {xs xs' : List α} {z : α} (h
 @[to_additive]
 theorem Multiset.prod_congr {α : Type _} [CommMonoid α] {xs : Multiset α} {xs' : List α} {z : α}
     (h₁ : xs = (xs' : Multiset α)) (h₂ : xs'.Prod = z) : xs.Prod = z := by
-  rw [← h₂, ← Multiset.coe_prod, h₁]
+  rw [← h₂, ← Multiset.prod_coe, h₁]
 #align tactic.norm_num.multiset.prod_congr Tactic.NormNum.Multiset.prod_congr
 #align tactic.norm_num.multiset.sum_congr Tactic.NormNum.Multiset.sum_congr
 
@@ -452,7 +452,7 @@ unsafe def list.prove_sum_map (β ef : expr) (xs : List expr) : tactic (expr ×
 theorem Finset.eval_prod_of_list {β α : Type _} [CommMonoid β] (s : Finset α) (f : α → β)
     {is : List α} (his : is.Nodup) (hs : Finset.mk (↑is) (Multiset.coe_nodup.mpr his) = s) {x : β}
     (hx : (is.map f).Prod = x) : s.Prod f = x := by
-  rw [← hs, Finset.prod_mk, Multiset.coe_map, Multiset.coe_prod, hx]
+  rw [← hs, Finset.prod_mk, Multiset.map_coe, Multiset.prod_coe, hx]
 #align tactic.norm_num.finset.eval_prod_of_list Tactic.NormNum.Finset.eval_prod_of_list
 #align tactic.norm_num.finset.eval_sum_of_list Tactic.NormNum.Finset.eval_sum_of_list

2fe465de

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,9 +3,9 @@ Copyright (c) 2022 Anne Baanen. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Anne Baanen
 -/
-import Mathbin.Algebra.BigOperators.Basic
-import Mathbin.Data.Int.Interval
-import Mathbin.Tactic.NormNum
+import Algebra.BigOperators.Basic
+import Data.Int.Interval
+import Tactic.NormNum
 
 #align_import algebra.big_operators.norm_num from "leanprover-community/mathlib"@"2fe465deb81bcd7ccafa065bb686888a82f15372"

2fe465de

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,16 +2,13 @@
 Copyright (c) 2022 Anne Baanen. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Anne Baanen
-
-! This file was ported from Lean 3 source module algebra.big_operators.norm_num
-! leanprover-community/mathlib commit 2fe465deb81bcd7ccafa065bb686888a82f15372
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Algebra.BigOperators.Basic
 import Mathbin.Data.Int.Interval
 import Mathbin.Tactic.NormNum
 
+#align_import algebra.big_operators.norm_num from "leanprover-community/mathlib"@"2fe465deb81bcd7ccafa065bb686888a82f15372"
+
 /-! ### `norm_num` plugin for big operators
 
 > THIS FILE IS SYNCHRONIZED WITH MATHLIB4.

2fe465de

bump to nightly-2023-07-16-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/2fe465deb81bcd7ccafa065bb686888a82f15372

bb547586

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Anne Baanen
 
 ! This file was ported from Lean 3 source module algebra.big_operators.norm_num
-! leanprover-community/mathlib commit 70fd9563a21e7b963887c9360bd29b2393e6225a
+! leanprover-community/mathlib commit 2fe465deb81bcd7ccafa065bb686888a82f15372
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -14,6 +14,9 @@ import Mathbin.Tactic.NormNum
 
 /-! ### `norm_num` plugin for big operators
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This `norm_num` plugin provides support for computing sums and products of
 lists, multisets and finsets.

70fd9563

bump to nightly-2023-06-08-23

mathlib commit https://github.com/leanprover-community/mathlib/commit/31c24aa72e7b3e5ed97a8412470e904f82b81004

d3cfe2e3

Diff

@@ -334,6 +334,7 @@ theorem List.prod_cons_congr {α : Type _} [Monoid α] (xs : List α) (x y z : 
 #align tactic.norm_num.list.sum_cons_congr Tactic.NormNum.List.sum_cons_congr
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+-- PLEASE REPORT THIS TO MATHPORT DEVS, THIS SHOULD NOT HAPPEN.
 -- failed to format: unknown constant 'term.pseudo.antiquot'
 /--
       Evaluate `list.prod %%xs`,
@@ -375,6 +376,7 @@ theorem List.prod_cons_congr {α : Type _} [Monoid α] (xs : List α) (x y z : 
 #align tactic.norm_num.list.prove_prod tactic.norm_num.list.prove_prod
 
 /- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+-- PLEASE REPORT THIS TO MATHPORT DEVS, THIS SHOULD NOT HAPPEN.
 -- failed to format: unknown constant 'term.pseudo.antiquot'
 /--
       Evaluate `list.sum %%xs`,

70fd9563

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

70fd9563

chore: Make Finset.preimage not depend on Finset.sum (#11601)

and Data.Finset.LocallyFinite not depend on Finset.sum too

d6a4b5d2

Diff

@@ -354,7 +354,7 @@ If your finset is not supported, you can add it to the match in `Finset.proveEmp
 -/
 @[norm_num @Finset.prod _ _ _ _ _]
 partial def evalFinsetProd : NormNumExt where eval {u β} e := do
-  let .app (.app (.app (.app (.app (.const `Finset.prod [_, v]) β') α) _) s) f ←
+  let .app (.app (.app (.app (.app (.const `Finset.prod [_, v]) α) β') _) s) f ←
     whnfR e | failure
   guard <| ← withNewMCtxDepth <| isDefEq β β'
   have α : Q(Type v) := α
@@ -383,7 +383,7 @@ If your finset is not supported, you can add it to the match in `Finset.proveEmp
 -/
 @[norm_num @Finset.sum _ _ _ _ _]
 partial def evalFinsetSum : NormNumExt where eval {u β} e := do
-  let .app (.app (.app (.app (.app (.const `Finset.sum [_, v]) β') α) _) s) f ←
+  let .app (.app (.app (.app (.app (.const `Finset.sum [_, v]) α) β') _) s) f ←
     whnfR e | failure
   guard <| ← withNewMCtxDepth <| isDefEq β β'
   have α : Q(Type v) := α

70fd9563

chore(LinearAlgebra,BigOperators): drop some decidability assumptions (#10237)

Found by a linter from #10235.

3646044d

Diff

@@ -171,9 +171,9 @@ def Multiset.ProveZeroOrConsResult.eq_trans {α : Q(Type u)} {s t : Q(Multiset $
   | .zero pf => .zero q(Eq.trans $eq $pf)
   | .cons a s' pf => .cons a s' q(Eq.trans $eq $pf)
 
-lemma Multiset.insert_eq_cons {α : Type*} [DecidableEq α] (a : α) (s : Multiset α) :
-    insert a s = Multiset.cons a s := by
-  ext; simp
+lemma Multiset.insert_eq_cons {α : Type*} (a : α) (s : Multiset α) :
+    insert a s = Multiset.cons a s :=
+  rfl
 
 lemma Multiset.range_zero' {n : ℕ} (pn : NormNum.IsNat n 0) :
     Multiset.range n = 0 := by rw [pn.out, Nat.cast_zero, Multiset.range_zero]

70fd9563

fix: add beta reduction in BigOperator norm_num extensions (#9446)

Inserts a call to Expr.betaRev in the cons case of evalFinsetBigop. This prevents norm_num from getting stuck on a beta redex applied to a nat literal, as currently happens in the third example below:

import Mathlib.Tactic.NormNum
import Mathlib.Tactic.NormNum.BigOperators

open BigOperators

-- works
example : (∑ i in Finset.range 10, (i^2 : ℕ)) = 285 := by norm_num1

-- also works (via the evalOfNat extension)
example : (∑ i in Finset.range 10, (OfNat.ofNat i)) = 45 := by norm_num1

-- does not work
example : (∑ i in Finset.range 10, i) = 45 := by norm_num1

Also, adds a test and removes some unnecessary parens from neighboring tests.

2297cb1e

Diff

@@ -341,7 +341,7 @@ partial def evalFinsetBigop {α : Q(Type u)} {β : Q(Type v)}
     match ← Finset.proveEmptyOrCons s with
     | .empty pf => pure <| res_empty.eq_trans q(congr_fun (congr_arg _ $pf) _)
     | .cons a s' h pf => do
-      let fa : Q($β) := Expr.app f a
+      let fa : Q($β) := Expr.betaRev f #[a]
       let res_fa ← derive fa
       let res_op_s' : Result q($op $s' $f) ← evalFinsetBigop op f res_empty @res_cons s'
       let res ← res_cons res_fa res_op_s'

70fd9563

chore: space after ← (#8178)

Co-authored-by: Moritz Firsching <firsching@google.com>

5fb9beab

Diff

@@ -356,7 +356,7 @@ If your finset is not supported, you can add it to the match in `Finset.proveEmp
 partial def evalFinsetProd : NormNumExt where eval {u β} e := do
   let .app (.app (.app (.app (.app (.const `Finset.prod [_, v]) β') α) _) s) f ←
     whnfR e | failure
-  guard <| ←withNewMCtxDepth <| isDefEq β β'
+  guard <| ← withNewMCtxDepth <| isDefEq β β'
   have α : Q(Type v) := α
   have s : Q(Finset $α) := s
   have f : Q($α → $β) := f
@@ -385,7 +385,7 @@ If your finset is not supported, you can add it to the match in `Finset.proveEmp
 partial def evalFinsetSum : NormNumExt where eval {u β} e := do
   let .app (.app (.app (.app (.app (.const `Finset.sum [_, v]) β') α) _) s) f ←
     whnfR e | failure
-  guard <| ←withNewMCtxDepth <| isDefEq β β'
+  guard <| ← withNewMCtxDepth <| isDefEq β β'
   have α : Q(Type v) := α
   have s : Q(Finset $α) := s
   have f : Q($α → $β) := f

70fd9563

fix: disable autoImplicit globally (#6528)

Autoimplicits are highly controversial and also defeat the performance-improving work in #6474.

The intent of this PR is to make autoImplicit opt-in on a per-file basis, by disabling it in the lakefile and enabling it again with set_option autoImplicit true in the few files that rely on it.

That also keeps this PR small, as opposed to attempting to "fix" files to not need it any more.

I claim that many of the uses of autoImplicit in these files are accidental; situations such as:

Assuming variables are in scope, but pasting the lemma in the wrong section
Pasting in a lemma from a scratch file without checking to see if the variable names are consistent with the rest of the file
Making a copy-paste error between lemmas and forgetting to add an explicit arguments.

Having set_option autoImplicit false as the default prevents these types of mistake being made in the 90% of files where autoImplicits are not used at all, and causes them to be caught by CI during review.

I think there were various points during the port where we encouraged porters to delete the universes u v lines; I think having autoparams for universe variables only would cover a lot of the cases we actually use them, while avoiding any real shortcomings.

A Zulip poll (after combining overlapping votes accordingly) was in favor of this change with 5:5:18 as the no:dontcare:yes vote ratio.

While this PR was being reviewed, a handful of files gained some more likely-accidental autoImplicits. In these places, set_option autoImplicit true has been placed locally within a section, rather than at the top of the file.

0c24f831

Diff

@@ -38,6 +38,8 @@ In particular, we can't use the plugin on sums containing variables.
    normalization?)
 -/
 
+set_option autoImplicit true
+
 namespace Mathlib.Meta
 
 open Lean hiding Rat mkRat

70fd9563

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -169,7 +169,7 @@ def Multiset.ProveZeroOrConsResult.eq_trans {α : Q(Type u)} {s t : Q(Multiset $
   | .zero pf => .zero q(Eq.trans $eq $pf)
   | .cons a s' pf => .cons a s' q(Eq.trans $eq $pf)
 
-lemma Multiset.insert_eq_cons {α : Type _} [DecidableEq α] (a : α) (s : Multiset α) :
+lemma Multiset.insert_eq_cons {α : Type*} [DecidableEq α] (a : α) (s : Multiset α) :
     insert a s = Multiset.cons a s := by
   ext; simp
 
@@ -238,7 +238,7 @@ def Finset.ProveEmptyOrConsResult.eq_trans {α : Q(Type u)} {s t : Q(Finset $α)
   | .empty pf => .empty q(Eq.trans $eq $pf)
   | .cons a s' h pf => .cons a s' h q(Eq.trans $eq $pf)
 
-lemma Finset.insert_eq_cons {α : Type _} [DecidableEq α] (a : α) (s : Finset α) (h : a ∉ s) :
+lemma Finset.insert_eq_cons {α : Type*} [DecidableEq α] (a : α) (s : Finset α) (h : a ∉ s) :
     insert a s = Finset.cons a s h := by
   ext; simp
 
@@ -249,7 +249,7 @@ lemma Finset.range_succ' {n nn n' : ℕ} (pn : NormNum.IsNat n nn) (pn' : nn = N
     Finset.range n = Finset.cons n' (Finset.range n') Finset.not_mem_range_self := by
   rw [pn.out, Nat.cast_id, pn', Finset.range_succ, Finset.insert_eq_cons]
 
-lemma Finset.univ_eq_elems {α : Type _} [Fintype α] (elems : Finset α)
+lemma Finset.univ_eq_elems {α : Type*} [Fintype α] (elems : Finset α)
     (complete : ∀ x : α, x ∈ elems) :
     Finset.univ = elems := by
   ext x; simpa using complete x
@@ -317,11 +317,11 @@ def Result.eq_trans {α : Q(Type u)} {a b : Q($α)} (eq : Q($a = $b)) : Result b
   | .isNegNat inst lit proof => Result.isNegNat inst lit q($eq ▸ $proof)
   | .isRat inst q n d proof => Result.isRat inst q n d q($eq ▸ $proof)
 
-protected lemma Finset.sum_empty {β α : Type _} [CommSemiring β] (f : α → β) :
+protected lemma Finset.sum_empty {β α : Type*} [CommSemiring β] (f : α → β) :
     IsNat (Finset.sum ∅ f) 0 :=
   ⟨by simp⟩
 
-protected lemma Finset.prod_empty {β α : Type _} [CommSemiring β] (f : α → β) :
+protected lemma Finset.prod_empty {β α : Type*} [CommSemiring β] (f : α → β) :
     IsNat (Finset.prod ∅ f) 1 :=
   ⟨by simp⟩

70fd9563

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,16 +2,13 @@
 Copyright (c) 2023 Anne Baanen. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Anne Baanen, Floris van Doorn
-
-! This file was ported from Lean 3 source module algebra.big_operators.norm_num
-! leanprover-community/mathlib commit 70fd9563a21e7b963887c9360bd29b2393e6225a
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Tactic.NormNum.Basic
 import Mathlib.Algebra.BigOperators.Basic
 import Mathlib.Data.List.FinRange
 
+#align_import algebra.big_operators.norm_num from "leanprover-community/mathlib"@"70fd9563a21e7b963887c9360bd29b2393e6225a"
+
 /-!
 # `norm_num` plugin for big operators

70fd9563

chore: bump quote4 (#5975)

d3b4f0c8

Diff

@@ -105,51 +105,44 @@ lemma List.range_succ_eq_map' {n nn n' : ℕ} (pn : NormNum.IsNat n nn) (pn' : n
     List.range n = 0 :: List.map Nat.succ (List.range n') := by
   rw [pn.out, Nat.cast_id, pn', List.range_succ_eq_map]
 
+set_option linter.unusedVariables false in
 /-- Either show the expression `s : Q(List α)` is Nil, or remove one element from it.
 
 Fails if we cannot determine which of the alternatives apply to the expression.
 -/
-partial def List.proveNilOrCons {α : Q(Type u)} :
-  (s : Q(List $α)) → MetaM (List.ProveNilOrConsResult s) :=
-  fun s =>
+partial def List.proveNilOrCons {α : Q(Type u)} (s : Q(List $α)) :
+    MetaM (List.ProveNilOrConsResult s) :=
   s.withApp fun e a =>
   match (e, e.constName, a) with
-  | (_, `EmptyCollection.EmptyCollection, _) => pure (.nil (q(rfl) : Q((∅ : List $α) = [])))
-  | (_, `List.nil, _) => pure (.nil (q(rfl) : Q(([] : List $α) = [])))
-  | (_, `List.cons, #[_, a, s']) => pure (.cons a s' (q(rfl) : Q($s = $s)))
-  | (_, `List.range, #[(n : Q(ℕ))]) => do
-    let instAMO_nat : Q(AddMonoidWithOne ℕ) := q(AddCommMonoidWithOne.toAddMonoidWithOne)
-    let ⟨nn, pn⟩ ← NormNum.deriveNat n
+  | (_, ``EmptyCollection.emptyCollection, _) => haveI : $s =Q {} := ⟨⟩; pure (.nil q(.refl []))
+  | (_, ``List.nil, _) => haveI : $s =Q [] := ⟨⟩; pure (.nil q(rfl))
+  | (_, ``List.cons, #[_, (a : Q($α)), (s' : Q(List $α))]) =>
+    haveI : $s =Q $a :: $s' := ⟨⟩; pure (.cons a s' q(rfl))
+  | (_, ``List.range, #[(n : Q(ℕ))]) =>
+    have s : Q(List ℕ) := s; .uncheckedCast _ _ <$> show MetaM (ProveNilOrConsResult s) from do
+    let ⟨nn, pn⟩ ← NormNum.deriveNat n _
+    haveI' : $s =Q .range $n := ⟨⟩
     let nnL := nn.natLit!
     if nnL = 0 then
-      let pn : Q(@NormNum.IsNat _ _ $n 0) := pn
-      return .nil (q(List.range_zero' $pn) : Q(List.range $n = []))
+      haveI' : $nn =Q 0 := ⟨⟩
+      return .nil q(List.range_zero' $pn)
     else
       have n' : Q(ℕ) := mkRawNatLit (nnL - 1)
-      let pn' : Q($nn = Nat.succ $n') := (q(Eq.refl $nn) : Expr)
-      return (List.ProveNilOrConsResult.cons
-        q(0)
-        q(List.map Nat.succ (List.range $n'))
-        q(List.range_succ_eq_map' $pn $pn')).uncheckedCast (q(List.range ($n)) : Q(List ℕ)) s
-  | (_, `List.finRange, #[(n : Q(ℕ))]) => do
-    match ← Nat.unifyZeroOrSucc n with -- We want definitional equality on `n`.
-    | .zero _pf => do
-      pure (.nil (q(List.finRange_zero) : Q(List.finRange 0 = [])))
-    | .succ n' _pf => pure <| ((List.ProveNilOrConsResult.cons
-        q(0 : Fin (Nat.succ $n'))
-        (q(List.map Fin.succ (List.finRange $n')))
-        (q(List.finRange_succ_eq_map $n'))).uncheckedCast
-          (q(List.finRange (Nat.succ $n')) : Q(List (Fin (Nat.succ $n'))))
-          s)
-  | (.const `List.map [v, _], _, #[β, _, f, xxs]) => do
-    have β : Q(Type v) := β
-    have f : Q($β → $α) := f
-    have xxs : Q(List $β) := xxs
-    match ← List.proveNilOrCons xxs with
-    | .nil pf => pure <| (.nil
-      (q($pf ▸ List.map_nil) : Q(List.map $f $xxs = [])))
-    | .cons x xs pf => pure <| (.cons q($f $x) q(List.map $f $xs)
-      (q($pf ▸ List.map_cons $f $x $xs) : Q(List.map $f $xxs = $f $x :: List.map $f $xs)))
+      have : $nn =Q .succ $n' := ⟨⟩
+      return .cons _ _ q(List.range_succ_eq_map' $pn (.refl $nn))
+  | (_, ``List.finRange, #[(n : Q(ℕ))]) =>
+    have s : Q(List (Fin $n)) := s
+    .uncheckedCast _ _ <$> show MetaM (ProveNilOrConsResult s) from do
+    haveI' : $s =Q .finRange $n := ⟨⟩
+    return match ← Nat.unifyZeroOrSucc n with -- We want definitional equality on `n`.
+    | .zero _pf => .nil q(List.finRange_zero)
+    | .succ n' _pf => .cons _ _ q(List.finRange_succ_eq_map $n')
+  | (.const ``List.map [v, _], _, #[(β : Q(Type v)), _, (f : Q($β → $α)), (xxs : Q(List $β))]) => do
+    haveI' : $s =Q ($xxs).map $f := ⟨⟩
+    return match ← List.proveNilOrCons xxs with
+    | .nil pf => .nil q(($pf ▸ List.map_nil : List.map _ _ = _))
+    | .cons x xs pf => .cons q($f $x) q(($xs).map $f)
+      q(($pf ▸ List.map_cons $f $x $xs : List.map _ _ = _))
   | (_, fn, args) =>
     throwError "List.proveNilOrCons: unsupported List expression {s} ({fn}, {args})"
 
@@ -194,33 +187,31 @@ lemma Multiset.range_succ' {n nn n' : ℕ} (pn : NormNum.IsNat n nn) (pn' : nn =
 
 Fails if we cannot determine which of the alternatives apply to the expression.
 -/
-partial def Multiset.proveZeroOrCons {α : Q(Type u)} :
-  (s : Q(Multiset $α)) → MetaM (Multiset.ProveZeroOrConsResult s) :=
-  fun s =>
-  match Expr.getAppFnArgs s with
-  | (`EmptyCollection.EmptyCollection, _) => pure (.zero (q(rfl) : Q((∅ : Multiset $α) = 0)))
-  | (`Zero.zero, _) => pure (.zero (q(rfl) : Q((0 : Multiset $α) = 0)))
-  | (`Multiset.cons, #[_, a, s']) => pure (.cons a s' (q(rfl) : Q($s = $s)))
-  | (`Multiset.ofList, #[_, (val : Q(List $α))]) => do
-    match ← List.proveNilOrCons val with
-    | .nil pf => pure <| .zero (q($pf ▸ Multiset.coe_nil) : Q(($val : Multiset $α) = 0))
-    | .cons a s' pf => do
-      return (.cons a q($s')
-        (q($pf ▸ Multiset.cons_coe $a $s') : Q(↑$val = Multiset.cons $a $s')))
-  | (`Multiset.range, #[(n : Q(ℕ))]) => do
-    let instAMO_nat : Q(AddMonoidWithOne ℕ) := q(AddCommMonoidWithOne.toAddMonoidWithOne)
-    let ⟨nn, pn⟩ ← NormNum.deriveNat n
+partial def Multiset.proveZeroOrCons {α : Q(Type u)} (s : Q(Multiset $α)) :
+    MetaM (Multiset.ProveZeroOrConsResult s) :=
+  match s.getAppFnArgs with
+  | (``EmptyCollection.emptyCollection, _) => haveI : $s =Q {} := ⟨⟩; pure (.zero q(rfl))
+  | (``Zero.zero, _) => haveI : $s =Q 0 := ⟨⟩; pure (.zero q(rfl))
+  | (``Multiset.cons, #[_, (a : Q($α)), (s' : Q(Multiset $α))]) =>
+    haveI : $s =Q .cons $a $s' := ⟨⟩
+    pure (.cons a s' q(rfl))
+  | (``Multiset.ofList, #[_, (val : Q(List $α))]) => do
+    haveI : $s =Q .ofList $val := ⟨⟩
+    return match ← List.proveNilOrCons val with
+    | .nil pf => .zero q($pf ▸ Multiset.coe_nil : Multiset.ofList _ = _)
+    | .cons a s' pf => .cons a q($s') q($pf ▸ Multiset.cons_coe $a $s' : Multiset.ofList _ = _)
+  | (``Multiset.range, #[(n : Q(ℕ))]) => do
+    have s : Q(Multiset ℕ) := s; .uncheckedCast _ _ <$> show MetaM (ProveZeroOrConsResult s) from do
+    let ⟨nn, pn⟩ ← NormNum.deriveNat n _
+    haveI' : $s =Q .range $n := ⟨⟩
     let nnL := nn.natLit!
     if nnL = 0 then
-      let pn : Q(@NormNum.IsNat _ _ $n 0) := pn
-      return .zero (q(Multiset.range_zero' $pn) : Q(Multiset.range $n = 0))
+      haveI' : $nn =Q 0 := ⟨⟩
+      return .zero q(Multiset.range_zero' $pn)
     else
       have n' : Q(ℕ) := mkRawNatLit (nnL - 1)
-      let pn' : Q($nn = Nat.succ $n') := (q(Eq.refl $nn) : Expr)
-      return (Multiset.ProveZeroOrConsResult.cons
-        n'
-        q(Multiset.range $n')
-        q(Multiset.range_succ' $pn $pn')).uncheckedCast (q(Multiset.range ($n)) : Q(Multiset ℕ)) s
+      haveI' : $nn =Q ($n').succ := ⟨⟩
+      return .cons _ _ q(Multiset.range_succ' $pn rfl)
   | (fn, args) =>
     throwError "Multiset.proveZeroOrCons: unsupported multiset expression {s} ({fn}, {args})"
 
@@ -270,13 +261,14 @@ lemma Finset.univ_eq_elems {α : Type _} [Fintype α] (elems : Finset α)
 
 Fails if we cannot determine which of the alternatives apply to the expression.
 -/
-partial def Finset.proveEmptyOrCons {α : Q(Type u)} :
-  (s : Q(Finset $α)) → MetaM (Finset.ProveEmptyOrConsResult s) :=
-  fun s =>
-  match Expr.getAppFnArgs s with
-  | (`EmptyCollection.emptyCollection, _) => pure (.empty (q(rfl) : Q($s = $s)))
-  | (`Finset.cons, #[_, a, s', h]) => pure (.cons a s' h (q(rfl) : Q($s = $s)))
-  | (`Finset.mk, #[_, (val : Q(Multiset $α)), (nd : Q(Multiset.Nodup $val))]) => do
+partial def Finset.proveEmptyOrCons {α : Q(Type u)} (s : Q(Finset $α)) :
+    MetaM (ProveEmptyOrConsResult s) :=
+  match s.getAppFnArgs with
+  | (``EmptyCollection.emptyCollection, _) => haveI : $s =Q {} := ⟨⟩; pure (.empty q(rfl))
+  | (``Finset.cons, #[_, (a : Q($α)), (s' : Q(Finset $α)), (h : Q(¬ $a ∈ $s'))]) =>
+    haveI : $s =Q .cons $a $s' $h := ⟨⟩
+    pure (.cons a s' h q(.refl $s))
+  | (``Finset.mk, #[_, (val : Q(Multiset $α)), (nd : Q(Multiset.Nodup $val))]) => do
     match ← Multiset.proveZeroOrCons val with
     | .zero pf => pure <| .empty (q($pf ▸ Finset.mk_zero) : Q(Finset.mk $val $nd = ∅))
     | .cons a s' pf => do
@@ -285,29 +277,24 @@ partial def Finset.proveEmptyOrCons {α : Q(Type u)} :
       let h' : Q($a ∉ $s') := q((Multiset.nodup_cons.mp $h).1)
       return (.cons a q(Finset.mk $s' $nd') h'
         (q($pf ▸ Finset.mk_cons $h) : Q(Finset.mk $val $nd = Finset.cons $a ⟨$s', $nd'⟩ $h')))
-  | (`Finset.range, #[(n : Q(ℕ))]) => do
-    let instAMO_nat : Q(AddMonoidWithOne ℕ) := q(AddCommMonoidWithOne.toAddMonoidWithOne)
-    let ⟨nn, pn⟩ ← NormNum.deriveNat n
+  | (``Finset.range, #[(n : Q(ℕ))]) =>
+    have s : Q(Finset ℕ) := s; .uncheckedCast _ _ <$> show MetaM (ProveEmptyOrConsResult s) from do
+    let ⟨nn, pn⟩ ← NormNum.deriveNat n _
+    haveI' : $s =Q .range $n := ⟨⟩
     let nnL := nn.natLit!
     if nnL = 0 then
-      let pn : Q(@NormNum.IsNat _ _ $n 0) := pn
-      return .empty (q(Finset.range_zero' $pn) : Q(Finset.range $n = {}))
+      haveI : $nn =Q 0 := ⟨⟩
+      return .empty q(Finset.range_zero' $pn)
     else
       have n' : Q(ℕ) := mkRawNatLit (nnL - 1)
-      let pn' : Q($nn = Nat.succ $n') := (q(Eq.refl $nn) : Expr)
-      return (Finset.ProveEmptyOrConsResult.cons
-        n'
-        (q(Finset.range $n'))
-        (q(@Finset.not_mem_range_self $n'))
-        (q(Finset.range_succ' $pn $pn'))).uncheckedCast
-          (q(Finset.range $n) : Q(Finset ℕ))
-          s
-  | (`Finset.univ, #[_, instFT]) => do
-    match Expr.getAppFnArgs (← whnfI instFT) with
-    | (`Fintype.mk, #[_, (elems : Q(Finset $α)), (complete : Q(∀ x : $α, x ∈ $elems))]) => do
-      have _instFT : Q(Fintype $α) := instFT
+      haveI' : $nn =Q ($n').succ := ⟨⟩
+      return .cons n' _ _ q(Finset.range_succ' $pn (.refl $nn))
+  | (``Finset.univ, #[_, (instFT : Q(Fintype $α))]) => do
+    haveI' : $s =Q .univ := ⟨⟩
+    match (← whnfI instFT).getAppFnArgs with
+    | (``Fintype.mk, #[_, (elems : Q(Finset $α)), (complete : Q(∀ x : $α, x ∈ $elems))]) => do
       let res ← Finset.proveEmptyOrCons elems
-      pure <| res.eq_trans (q(Finset.univ_eq_elems $elems $complete) : Q(Finset.univ = $elems))
+      pure <| res.eq_trans q(Finset.univ_eq_elems $elems $complete)
     | e =>
       throwError "Finset.proveEmptyOrCons: could not determine elements of Fintype instance {e}"
   | (fn, args) =>
@@ -374,7 +361,7 @@ partial def evalFinsetProd : NormNumExt where eval {u β} e := do
   have α : Q(Type v) := α
   have s : Q(Finset $α) := s
   have f : Q($α → $β) := f
-  let instCS ← synthInstanceQ (q(CommSemiring $β) : Q(Type u)) <|>
+  let instCS : Q(CommSemiring $β) ← synthInstanceQ q(CommSemiring $β) <|>
     throwError "not a commutative semiring: {β}"
   let instS : Q(Semiring $β) := q(CommSemiring.toSemiring)
   -- Have to construct this expression manually, `q(1)` doesn't parse correctly:
@@ -384,7 +371,7 @@ partial def evalFinsetProd : NormNumExt where eval {u β} e := do
 
   evalFinsetBigop q(Finset.prod) f res_empty (fun {a s' h} res_fa res_prod_s' ↦ do
       let fa : Q($β) := Expr.app f a
-      let res : Result _ ← evalMul.core q($fa * Finset.prod $s' $f) q((· * ·)) _ _ instS res_fa
+      let res ← evalMul.core q($fa * Finset.prod $s' $f) q(HMul.hMul) _ _ instS res_fa
         res_prod_s'
       let eq : Q(Finset.prod (Finset.cons $a $s' $h) $f = $fa * Finset.prod $s' $f) :=
         q(Finset.prod_cons $h)
@@ -403,15 +390,15 @@ partial def evalFinsetSum : NormNumExt where eval {u β} e := do
   have α : Q(Type v) := α
   have s : Q(Finset $α) := s
   have f : Q($α → $β) := f
-  let instCS ← synthInstanceQ (q(CommSemiring $β) : Q(Type u)) <|>
+  let instCS : Q(CommSemiring $β) ← synthInstanceQ q(CommSemiring $β) <|>
     throwError "not a commutative semiring: {β}"
-  let n : Q(ℕ) := q(0)
+  let n : Q(ℕ) := mkRawNatLit 0
   let pf : Q(IsNat (Finset.sum ∅ $f) $n) := q(@Finset.sum_empty $β $α $instCS $f)
   let res_empty := Result.isNat _ n pf
 
   evalFinsetBigop q(Finset.sum) f res_empty (fun {a s' h} res_fa res_sum_s' ↦ do
       let fa : Q($β) := Expr.app f a
-      let res : Result _ ← evalAdd.core q($fa + Finset.sum $s' $f) q((· + ·)) _ _ res_fa res_sum_s'
+      let res ← evalAdd.core q($fa + Finset.sum $s' $f) q(HAdd.hAdd) _ _ res_fa res_sum_s'
       let eq : Q(Finset.sum (Finset.cons $a $s' $h) $f = $fa + Finset.sum $s' $f) :=
         q(Finset.sum_cons $h)
       pure <| res.eq_trans eq)

70fd9563

chore: tidy various files (#5971)

bb6d52f7

Diff

@@ -69,7 +69,7 @@ def Nat.unifyZeroOrSucc (n : Q(ℕ)) : MetaM (Nat.UnifyZeroOrSuccResult n) := do
     let n' : Q(ℕ) ← mkFreshExprMVar q(ℕ)
     let ⟨(_pf : $n =Q Nat.succ $n')⟩ ← assertDefEqQ n q(Nat.succ $n')
     let (.some (n'_val : Q(ℕ))) ← getExprMVarAssignment? n'.mvarId! |
-      throwError "could not figure out value of `?n` from `{n} =?= nat.succ ?n`"
+      throwError "could not figure out value of `?n` from `{n} =?= Nat.succ ?n`"
     pure (.succ n'_val ⟨⟩)
 
 /-- This represents the result of trying to determine whether the given expression

70fd9563

feat: basic big operator plugin for norm_num (#4350)

I wrote a basic implementation for a norm_num plugin evaluating Finset.sum and Finset.prod. It does not yet support as many Finset expressions as the Mathlib 3 implementation, and it cannot deal with variables appearing in the sum. I believe it's valuable to have this implementation since we do use this plugin in various parts of mathlib.

Co-authored-by: Anne Baanen <Vierkantor@users.noreply.github.com> Co-authored-by: Anne Baanen <t.baanen@vu.nl> Co-authored-by: Jeremy Tan Jie Rui <reddeloostw@gmail.com>

cefb050f

`algebra.big_operators.norm_num` ⟷ `Mathlib.Tactic.NormNum.BigOperators`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 7 + 229

algebra.big_operators.norm_num ⟷ Mathlib.Tactic.NormNum.BigOperators

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 7 + 229

`algebra.big_operators.norm_num` ⟷ `Mathlib.Tactic.NormNum.BigOperators`