[Merged by Bors] - refactor(*): kill nat multiplication diamonds#7084
[Merged by Bors] - refactor(*): kill nat multiplication diamonds#7084
Conversation
|
I think the 20 or so |
Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
We need only change them if it is important for defeqness issues in diamonds for the nat scalar multiplication. This means it is only relevant when one defines a new type which might also get a |
|
No, as I said on Zulip coying just the data fields make things slower!!! |
|
Thanks 🎉 bors merge p=37 |
An `add_monoid` has a natural `ℕ`-action, defined by `n • a = a + ... + a`, that we want to declare as an instance as it makes it possible to use the language of linear algebra. However, there are often other natural `ℕ`-actions. For instance, for any semiring `R`, the space of polynomials `polynomial R` has a natural `R`-action defined by multiplication on the coefficients. This means that `polynomial ℕ` has two natural `ℕ`-actions, which are equal but not defeq. The same goes for linear maps, tensor products, and so on (and even for `ℕ` itself). This is the case on current mathlib, with such non-defeq diamonds all over the place. To solve this issue, we embed an `ℕ`-action in the definition of an `add_monoid` (which is by default the naive action `a + ... + a`, but can be adjusted when needed -- it should always be equal to this one, but not necessarily definitionally), and declare a `has_scalar ℕ α` instance using this action. This is yet another example of the forgetful inheritance pattern that we use in metric spaces, embedding a topology and a uniform structure in it (except that here the functor from additive monoids to nat-modules is faithful instead of forgetful, but it doesn't make a difference). More precisely, we define ```lean def nsmul_rec [has_add M] [has_zero M] : ℕ → M → M | 0 a := 0 | (n+1) a := nsmul_rec n a + a class add_monoid (M : Type u) extends add_semigroup M, add_zero_class M := (nsmul : ℕ → M → M := nsmul_rec) (nsmul_zero' : ∀ x, nsmul 0 x = 0 . try_refl_tac) (nsmul_succ' : ∀ (n : ℕ) x, nsmul n.succ x = nsmul n x + x . try_refl_tac) ``` For example, when we define `polynomial R`, then we declare the `ℕ`-action to be by multiplication on each coefficient (using the `ℕ`-action on `R` that comes from the fact that `R` is an `add_monoid`). In this way, the two natural `has_scalar ℕ (polynomial ℕ)` instances are defeq. The tactic `to_additive` transfers definitions and results from multiplicative monoids to additive monoids. To work, it has to map fields to fields. This means that we should also add corresponding fields to the multiplicative structure `monoid`, which could solve defeq problems for powers if needed. These problems do not come up in practice, so most of the time we will not need to adjust the `npow` field when defining multiplicative objects. With this refactor, all the diamonds are gone. Or rather, all the diamonds I noticed are gone, but if there are still some diamonds then they can be fixed, contrary to before. Also, the notation `•ℕ` is gone, just use `•`. Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
| /-- All `ℕ`-semimodule structures are equal. -/ | ||
| instance add_comm_monoid.nat_semimodule.subsingleton : subsingleton (semimodule ℕ M) := | ||
| ⟨λ P Q, by { | ||
| ext n, | ||
| rw [←nsmul_eq_smul, ←nsmul_eq_smul], }⟩ |
There was a problem hiding this comment.
Is there a reason for removing this? It seems like a nice statement to have to justify the design, even if it's not really needed any more.
(obviously let's not stop the build, but I think we should add this back)
|
Pull request successfully merged into master. Build succeeded: |
…id.nat_semimodule.subsingleton (#7263) As suggested in #7084 (comment). Even if we now have a design solution that makes this unnecessary, it still feels like a result worth stating.
Insert a data field `gsmul` in `add_comm_group` containing a Z-action, and use it to make sure that all diamonds related to `Z` -actions disappear. Followup to #7084 Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com>
…2072) `continuous_linear_map.continuous_nsmul` is nothing to do with `continuous_linear_map`s, and is the same as `continuous_nsmul`, but the latter doesn't require commutativity. There is no reason to keep the former. This lemma was added in #7084, but probably got missed due to how large that PR had to be. We can't remove `continuous_linear_map.continuous_zsmul` until #12055 is merged, as there is currently no `continuous_zsmul` in the root namespace.
An
add_monoidhas a naturalℕ-action, defined byn • a = a + ... + a, that we want to declareas an instance as it makes it possible to use the language of linear algebra. However, there are
often other natural
ℕ-actions. For instance, for any semiringR, the space of polynomialspolynomial Rhas a naturalR-action defined by multiplication on the coefficients. This meansthat
polynomial ℕhas two naturalℕ-actions, which are equal but not defeq. The samegoes for linear maps, tensor products, and so on (and even for
ℕitself). This is the case on currentmathlib, with such non-defeq diamonds all over the place.
To solve this issue, we embed an
ℕ-action in the definition of anadd_monoid(which is bydefault the naive action
a + ... + a, but can be adjusted when needed -- it should always be equalto this one, but not necessarily definitionally), and declare
a
has_scalar ℕ αinstance using this action. This is yet another example of the forgetful inheritancepattern that we use in metric spaces, embedding a topology and a uniform structure in it (except that
here the functor from additive monoids to nat-modules is faithful instead of forgetful, but it doesn't
make a difference).
More precisely, we define
For example, when we define
polynomial R, then we declare theℕ-action to be by multiplicationon each coefficient (using the
ℕ-action onRthat comes from the fact thatRisan
add_monoid). In this way, the two naturalhas_scalar ℕ (polynomial ℕ)instances are defeq.The tactic
to_additivetransfers definitions and results from multiplicative monoids to additivemonoids. To work, it has to map fields to fields. This means that we should also add corresponding
fields to the multiplicative structure
monoid, which could solve defeq problems for powers ifneeded. These problems do not come up in practice, so most of the time we will not need to adjust
the
npowfield when defining multiplicative objects.With this refactor, all the diamonds are gone. Or rather, all the diamonds I noticed are gone, but if
there are still some diamonds then they can be fixed, contrary to before.
Also, the notation
•ℕis gone, just use•.TODO: do the same for
ℤ. In another PR, let's keep this one reasonable.The main pain points in the refactor are the following:
we have to adjust the definition of
powto make sure thatto_additiveworks. In particular,a ^ 0is not any more defeq to1, anda^ (n+1)is not any more defeq toa * a ^ n. Many proofs were using this, so I had to add a lot ofrw pow_zeroandrw pow_succ. I don't think it's a problem: relying on anecdotal defeqs in proofs is just prone to breaking. To me, the only place where defeq really matters is where the user has no control on it, i.e., on typeclass diamonds.to construct structures,
refineandrefine_structare often perturbed by opt_params and auto_params that need a typeclass which is not already declared. Here, the autoparam field(nsmul : ℕ → M → M := nsmul_rec)requires typeclasseshas_zero Mandhas_add M, that Lean core somehow provides when declaring the full structure, but when usingrefineorrefine_structthis is not so clear, and there are issues with metavariables left. In some situations, it worked fine, and sometimes not. The most efficient way I found is to userefine_struct, and fill thensmulfield likensmul := @nsmul_rec _ ⟨0⟩ ⟨(+)⟩,replacing the autoparam by hand.