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)

Defined in Data.Number.CalkinWilf

Methods

succ :: CalkinWilf a -> CalkinWilf a

pred :: CalkinWilf a -> CalkinWilf a

toEnum :: Int -> CalkinWilf a

fromEnum :: CalkinWilf a -> Int

enumFrom :: CalkinWilf a -> [CalkinWilf a]

enumFromThen :: CalkinWilf a -> CalkinWilf a -> [CalkinWilf a]

enumFromTo :: CalkinWilf a -> CalkinWilf a -> [CalkinWilf a]

enumFromThenTo :: CalkinWilf a -> CalkinWilf a -> CalkinWilf a -> [CalkinWilf a]

Eq a => Eq (CalkinWilf a)

Defined in Data.Number.CalkinWilf

Methods

(==) :: CalkinWilf a -> CalkinWilf a -> Bool

(/=) :: CalkinWilf a -> CalkinWilf a -> Bool

Integral a => Fractional (CalkinWilf a)

Defined in Data.Number.CalkinWilf

Methods

(/) :: CalkinWilf a -> CalkinWilf a -> CalkinWilf a

recip :: CalkinWilf a -> CalkinWilf a

fromRational :: Rational -> CalkinWilf a

Integral a => Num (CalkinWilf a)

Defined in Data.Number.CalkinWilf

Methods

(+) :: CalkinWilf a -> CalkinWilf a -> CalkinWilf a

(-) :: CalkinWilf a -> CalkinWilf a -> CalkinWilf a

(*) :: CalkinWilf a -> CalkinWilf a -> CalkinWilf a

negate :: CalkinWilf a -> CalkinWilf a

abs :: CalkinWilf a -> CalkinWilf a

signum :: CalkinWilf a -> CalkinWilf a

fromInteger :: Integer -> CalkinWilf a

Integral a => Ord (CalkinWilf a)

Defined in Data.Number.CalkinWilf

Methods

compare :: CalkinWilf a -> CalkinWilf a -> Ordering

(<) :: CalkinWilf a -> CalkinWilf a -> Bool

(<=) :: CalkinWilf a -> CalkinWilf a -> Bool

(>) :: CalkinWilf a -> CalkinWilf a -> Bool

(>=) :: CalkinWilf a -> CalkinWilf a -> Bool

max :: CalkinWilf a -> CalkinWilf a -> CalkinWilf a

min :: CalkinWilf a -> CalkinWilf a -> CalkinWilf a

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

Defined in Data.Number.CalkinWilf

Methods

readsPrec :: Int -> ReadS (CalkinWilf a)

readList :: ReadS [CalkinWilf a]

readPrec :: ReadPrec (CalkinWilf a)

readListPrec :: ReadPrec [CalkinWilf a]

Integral a => Real (CalkinWilf a)

Defined in Data.Number.CalkinWilf

Methods

toRational :: CalkinWilf a -> Rational

Integral a => RealFrac (CalkinWilf a)

Defined in Data.Number.CalkinWilf

Methods

properFraction :: Integral b => CalkinWilf a -> (b, CalkinWilf a)

truncate :: Integral b => CalkinWilf a -> b

round :: Integral b => CalkinWilf a -> b

ceiling :: Integral b => CalkinWilf a -> b

floor :: Integral b => CalkinWilf a -> b

Show a => Show (CalkinWilf a)

Defined in Data.Number.CalkinWilf

Methods

showsPrec :: Int -> CalkinWilf a -> ShowS

show :: CalkinWilf a -> String

showList :: [CalkinWilf a] -> ShowS

Integral a => Enum (CalkinWilf a)

Defined in Data.Number.CalkinWilf

Methods

toEnum :: Int -> Maybe (CalkinWilf a)

fromEnum :: CalkinWilf a -> Maybe Int

enumFromThen :: CalkinWilf a -> CalkinWilf a -> [CalkinWilf a]

enumFromThenTo :: CalkinWilf a -> CalkinWilf a -> CalkinWilf a -> [CalkinWilf a]

Integral a => DownwardEnum (CalkinWilf a)

Defined in Data.Number.CalkinWilf

Methods

pred :: CalkinWilf a -> Maybe (CalkinWilf a)

precedes :: CalkinWilf a -> CalkinWilf a -> Bool

enumDownFrom :: CalkinWilf a -> [CalkinWilf a]

enumDownFromTo :: CalkinWilf a -> CalkinWilf a -> [CalkinWilf a]

Integral a => UpwardEnum (CalkinWilf a)

Defined in Data.Number.CalkinWilf

Methods

succ :: CalkinWilf a -> Maybe (CalkinWilf a)

succeeds :: CalkinWilf a -> CalkinWilf a -> Bool

enumFrom :: CalkinWilf a -> [CalkinWilf a]

enumFromTo :: CalkinWilf a -> CalkinWilf a -> [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.