Recursive Data types in sml

Question

Is there a way define a datatype for whole numbers. i.e. 0,1,2,... not zero, one ,... individually.

I want to define the set of whole numbers. bu using 0, n,n+1 with recursion. I tried something like this: datatype nat=0|n|n+1 . But it was nearly obvious not to work because it does not recognize 0 as integer right?

I would appreciate any help.

Answer 1

Since the set of natural numbers is countably infinite, you can't enumerate all the cases.

You can represent natural numbers conceptually by Peano numbers:

datatype peano = Zero | Succ of peano

The datatype is very simple, it only defines 0 and ensures that each natural number has a successor. For example, 2 is actually represented as Succ (Succ Zero).

fun count Zero = 0
  | count (Succ p) = 1 + count p

Use similar techniques, you can build up add, sub, mult functions like you have with natural numbers.