6

I can compare two natural numbers by writing comparator manually:

is-≤ : ℕ → ℕ → Bool
is-≤ zero _ = true
is-≤ (suc _) zero = false
is-≤ (suc x) (suc y) = is-≤ x y

However, I hope that there is something similar in the standard library so I don't write that every time.

I was able to find _≤_ operator in Data.Nat, but it's a parametrized type which basically contains "proof" that one specific number is less than the other (similar to _≡_). Is there a way to use it or something else to understand which number is smaller than the other "in runtime" (e.g. return corresponding Bool)?

The bigger problem I'm trying to solve:

  1. As a part of my assignment, I'm writing a readNat : List Char → Maybe (ℕ × List Char) function. It tries to read natural number from the beginning of the list; will later become part of sscanf.
  2. I want to implement digit : Char → Maybe ℕ helper function which would parse a single decimal digit.
  3. In order to do so I want to compare primCharToNat c with primCharToNat '0', primCharToNat '1' and decide whether to return None or (primCharToNat c) ∸ (primCharToNat '0')
1
  • 1
    In the module you've found there's a proof _≤?_ that _≤_ is decidable. You can use that instead of a Boolean function.
    – gallais
    Oct 12, 2017 at 13:25

1 Answer 1

6

A solution suggested by @gallais in comments:

open import Data.Nat using (ℕ; _≤?_)
open import Data.Bool using (Bool)
open import Relation.Nullary using (Dec)

is-≤ : ℕ → ℕ → Bool
is-≤ a b with a ≤? b
... | Dec.yes _ = Bool.true
... | Dec.no _ = Bool.false

Here we match on a proof that _≤_ is decidable using the with-clause. One can use it similarly in more complex functions.

Suggestion by @user3237465 in comments to this answer: you can also use shorthand ⌊_⌋ (\clL/\clR or \lfloor/\rfloor) which does this exact pattern matching and eliminate the need for is-≤:

open import Data.Nat using (ℕ; _≤?_)
open import Data.Bool using (Bool)
open import Relation.Nullary.Decidable using (⌊_⌋)

is-≤ : ℕ → ℕ → Bool
is-≤ a b = ⌊ a ≤? b ⌋

Another approach is to use compare, it also provides more information (e.g. the difference between two numbers):

open import Data.Nat using (ℕ; compare)
open import Data.Bool using (Bool)
open import Relation.Nullary using (Dec)

is-≤' : ℕ → ℕ → Bool
is-≤' a b with compare a b
... | Data.Nat.greater _ _ = Bool.false
... | _ = Bool.true

is-≤3' : ℕ → Bool
is-≤3' a with 3 | compare a 3
... | _ | Data.Nat.greater _ _ = Bool.false
... | _ | _ = Bool.true

Note that compareing with a constant value requires extra caution for some reason.

1
  • 5
    You can write if ⌊ a ≤? b ⌋ then blah1 else blah2, where ⌊_⌋ comes from the Relation.Nullary.Decidable module. I usually define a type class like this. Oct 13, 2017 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.