Copyright	2012--2015 wren gayle romano
License	BSD3
Maintainer	wren@community.haskell.org
Stability	provisional
Portability	Haskell98 + CPP + GeneralizedNewtypeDeriving
Safe Haskell	Trustworthy
Language	Haskell98

Data.Number.CalkinWilf

Description

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

Synopsis

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) #
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) #
Methods (==) :: CalkinWilf a -> CalkinWilf a -> Bool # (/=) :: CalkinWilf a -> CalkinWilf a -> Bool #
Integral a => Fractional (CalkinWilf a) #
Methods (/) :: CalkinWilf a -> CalkinWilf a -> CalkinWilf a # recip :: CalkinWilf a -> CalkinWilf a # fromRational :: Rational -> CalkinWilf a #
Integral a => Num (CalkinWilf a) #
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) #
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 #
(Read a, Integral a) => Read (CalkinWilf a) #
Methods readsPrec :: Int -> ReadS (CalkinWilf a) # readList :: ReadS [CalkinWilf a] # readPrec :: ReadPrec (CalkinWilf a) # readListPrec :: ReadPrec [CalkinWilf a] #
Integral a => Real (CalkinWilf a) #
Methods toRational :: CalkinWilf a -> Rational #
Integral a => RealFrac (CalkinWilf a) #
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) #
Methods showsPrec :: Int -> CalkinWilf a -> ShowS # show :: CalkinWilf a -> String # showList :: [CalkinWilf a] -> ShowS #
Integral a => Enum (CalkinWilf a) #
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) #
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) #
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.