Data.Number.CalkinWilf

Enumerate the rationals in Calkin--Wilf order. That is, when we give enumeration a well-specified meaning (as Prelude.SafeEnum does) this renders instances for Ratio problematic. Ratio instances can be provided so long as the base type is integral and enumerable; but they must be done in an obscure order that does not coincide with the Ord instance for Ratio. Since this is not what people may expect, we only provide an instance for the newtype CalkinWilf, not for Ratio itself.

• Jeremy Gibbons, David Lester, and Richard Bird (2006). Enumerating the Rationals. JFP 16(3):281--291. DOI:10.1017/S0956796806005880 http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf

Documentation

newtype CalkinWilf a

Enumerate the rationals in Calkin--Wilf order. The enumeration is symmetric about zero, ensuring that all the negative rationals come before zero and all the positive rationals come after zero.

BUG: while the succeeds, precedes, toEnum, and fromEnum methods are correct, they are horribly inefficient. This can be rectified (or at least mitigated), but this remains to be done.

Constructors

CalkinWilf (Ratio a)

Instances

Integral a => Enum (CalkinWilf a)

Eq a => Eq (CalkinWilf a)

Integral a => Fractional (CalkinWilf a)

Integral a => Num (CalkinWilf a)

Integral a => Ord (CalkinWilf a)

(Integral a, Read a) => Read (CalkinWilf a)

Integral a => Real (CalkinWilf a)

Integral a => RealFrac (CalkinWilf a)

(Integral a, Show a) => Show (CalkinWilf a)

Integral a => Enum (CalkinWilf a)

Integral a => DownwardEnum (CalkinWilf a)

Integral a => UpwardEnum (CalkinWilf a)

unCalkinWilf :: CalkinWilf a -> Ratio a

Return the underlying Ratio. Not using record syntax to define this in order to pretty up the derived Show instance.