Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Suggestion for Integer in Standard library #1

Closed
UlfNorell opened this issue Jan 17, 2014 · 1 comment
Closed

Suggestion for Integer in Standard library #1

UlfNorell opened this issue Jan 17, 2014 · 1 comment

Comments

@UlfNorell
Copy link
Member

Reported by [email protected], Jan 10, 2014

The following is suggested for Data.Sign.Properties and
Data.Integer, Data.Integer.Properties.

  1. For Data.Sign :

    _s-assoc : Associative _s
    _s-comm : Commutative _s
    *s-invol : (s : Sign) → s *s s ≡ Sign.+

This is for *s = Sign.*.
I use these lemmata, and they are evidently of a general use.

  1. For Data.Integer, Data.Integer.Properties :

divMod is desirable for division with remainder, with proofs.

It can be lifted from Nat.DivMod.divMod.
But this lift still needs implementation.

For example, I need

decDivide : (x y : ℤ) → Dec $ RightQuotient intSetoid * x y

-- which also returns proof/disprove for \exist \q -> y * q == y.
It can be either by calling Integer.divMod
or by lifting to ℤ from a similar decDivide-Nat for Nat.
My implementation for this lifting takes about 200 lines
(despite that the subject looks trivial).

I think, Integer.divMod will help in this and in many other cases,
and I suspect that its lifting to ℤ will take not less than 100 lines.

  1. The following are useful :

    negneg : (x : ℤ) → - (- x) ≡ + x

    x+◃ : (m : ℕ) → (Sign.+ ◃ m) ≡ + m
    -◃ : (m : ℕ) → (Sign.- ◃ m) ≡ - (+ m)

    +m*+n= : (m n : ℕ) → (+ m) * (+ n) ≡ + (m *n n)

    -*- : (x y : ℤ) → (- x) * (- y) ≡ x * y

    s◃m*s'◃n : (s s' : Sign) → (m n : ℕ) →
    (s ◃ m ) * (s' ◃ n) ≡ (s *s s') ◃ (m *n n)

(for the last one I have a proof of about 30 lines).

@MatthewDaggitt
Copy link
Contributor

The requested lemmas have been added in 1695680 and 9946556

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants