[Agda] It feels like there isn't a way to do a partial
subtraction nicely ... and a feature suggestion :)
Tristan Wibberley
tristan at wibberley.org
Mon Mar 24 04:44:06 CET 2008
On Sun, 2008-03-23 at 20:28 +0100, Ulf Norell wrote:
> Defining True to be the record type with no fields is what's going to
> make this possible. Records support eta equality, which means that any
> record element "r" is equal to the record build by projecting the
> fields of "r". In the case of True this means that any element of True
> is equal to any other element of True. In particular, if the type
> checker is trying to find something of type True there's only one
> choice. Now, instead of defining NatLTE inductively you can define it
> recursively:
>
> NatLTE : Nat -> Nat -> Set
> NatLTE zero m = True
> NatLTE (suc n) zero = False
> NatLTE (suc n) (suc m) = NatLTE n m
>
> The type of minus is what you suggest:
>
> _-_ : (a : Nat) -> (b : Nat) -> {c : NatLTE b a} -> Nat
> _-_ m zero = m
> _-_ zero (suc _) {} -- there can be no proof here
> _-_ (suc n) (suc m) {p} = _-_ n m {p}
> -- a proof that suc n =< suc m is the same as a proof that n =<
> m
Do you mind if I add this to the documentation section of the wiki?
I'll make a howto section to which other high-level templates can be
added.
--
Tristan Wibberley
Any opinion expressed is mine (or else I'm playing devils advocate for
the sake of a good argument). My employer had nothing to do with this
communication.
More information about the Agda
mailing list