[Agda] Defining subtraction for naturals

wren ng thornton wren at freegeek.org
Thu Mar 17 19:35:59 CET 2011


Another question on particulars. When dealing with natural numbers, we 
run into the problem of defining subtraction. There are a few reasonable 
definitions:

(1) If the result would drop below zero then throw an overflow error;

(2) Use saturating subtraction, i.e. if the result would drop below zero 
then return zero;

(3) Use type hackery to disallow performing subtraction when the result 
would drop below zero, e.g. by requiring a proof that the left argument 
is not less than the right.

Dependently typed languages tend to use the second definition because it 
gives a pure total function (unlike the first) and because it's less 
obnoxious to use than the third. In Haskell the third would be even more 
obnoxious.

So my question is, mathematically speaking, is there any reason to 
prefer the second option over the first or third? Purity aside, I mean; 
do the natural numbers with saturating subtraction form any interesting 
mathematical object, or is it just what we're stuck with?


In a similar vein. Given a finite set (e.g., the natural numbers with 
some finite upper bound) and assuming we've already decided not to use 
modular arithmetic, is there any mathematical reason to prefer 
saturating addition and/or multiplication instead of throwing an 
overflow error?

-- 
Live well,
~wren


More information about the Agda mailing list