Is it possible to create a recursive data type with rational numbers like -> data Nat = Zero | Succ Nat?

Viewed 347

Is it possible to create a recursive data for rational numbers? I saw this one for natural numbers

data Nat = Zero | Succ Nat

I probably need to use two numbers for the ratio? But something like Zero,Zero doesnt work.

Thanks!

1 Answers

Positive rational numbers

We can define it like:

data Nat0 = One | Succ0 Nat0
data Nat = Zero | Succ Nat
data PosRational = PosRational Nat Nat0

so here we use two data types Nat0 (excluding zero), and Nat (including zero) that are defined recursively, and a data type PosRational that takes a Nat and Nat0 (so a numerator, and a denominator).

Including negative rational numbers

We can also include negative rational numbers, for instance by defining:

data Z = Pos Nat | Neg Nat0

and then define our Rational as:

data Rational = Rational Z Nat0

Countability of ℚ

Nevertheless we actually do not need that (given we do not need fast access to the numerator and denominator). Rational numbers are countable. We can enumerate all of them with the following scheme [source]:

countability of rational numbers

So we can simply define it as:

data Rational = Zero | NextRational Rational

Basically, every countable set can use this definition, so ℕ, ℤ, ℙ, ℚ, etc.

Related