[Agda] fastCompare for Nat
Sergei Meshveliani
mechvel at botik.ru
Wed Mar 27 18:38:20 CET 2019
Dear standard library developers,
The comparison Nat.<-cmp is `exponentially' slow.
As lib-0.18-candidate has fast _≡ᵇ_ and _<ᵇ_,
and as _≟_ is also fast on Nat (when the proof is not inspected),
this gives a hope for making <-cmp fast in a similar sense.
The below compareFast implements the goal by using that _∸_ is
expressed via built-in.
I wonder of whether standard library supports a simpler solution.
If it does not, then maybe it could incorporate a similar thing.
Thanks,
------
Sergei
--------------------------------------------------------------
compareFast : (m n : ℕ) → Tri (m < n) (m ≡ n) (m > n)
--
-- _≟_ and _∸_ are via built-in.
compareFast m n = aux (m ≟ n) (m ∸ n) (n ∸ m) refl refl
where
aux : Dec (m ≡ n) → (d d' : ℕ) → m ∸ n ≡ d → n ∸ m ≡ d' →
Tri (m < n) (m ≡ n) (m > n)
aux (yes m≡n) _ _ _ _ = tri≈ (<-irrefl m≡n) m≡n m≯n
where
m≯n = <-irrefl (sym m≡n)
aux (no m≢n) 0 _ m∸n≡0 _ = tri< m<n m≢n (<-asym m<n)
where
m≤n = m∸n≡0⇒m≤n m∸n≡0
m<n = ≤,≢⇒< m≤n m≢n
aux (no m≢n) (suc _) 0 _ n∸m≡0 =
tri> (<-asym n<m) m≢n n<m
where
n≤m = m∸n≡0⇒m≤n n∸m≡0
n≢m = m≢n ∘ sym
n<m = ≤,≢⇒< n≤m n≢m
aux _ (suc d₁) (suc d₂) m∸n≡1+d₁ n∸m≡1+d₂ =
contradiction n<m (<-asym m<n)
where
m∸n≢0 = \m-n≡0 → let 1+d₁≡0 = trans (sym m∸n≡1+d₁) m-n≡0
in suc≢0 1+d₁≡0
n∸m≢0 = \n-m≡0 → let 1+d₂≡0 = trans (sym n∸m≡1+d₂) n-m≡0
in suc≢0 1+d₂≡0
n<m = m∸n≢0⇒n<m {m} {n} m∸n≢0
m<n = m∸n≢0⇒n<m n∸m≢0
More information about the Agda
mailing list