Quotient.hs

-- Like Ratio but not broken.
module Quotient
  ( Quotient
  , quotient
  , unsafeQuotient
  , (%)
  , numerator
  , denominator
  , fromRatio
  , toRatio
  ) where

import qualified Data.Ratio as Ratio
import qualified GHC.Stack as Stack

data Quotient a = Q !a !a deriving (Eq, Read, Show)

quotient :: Integral a => a -> a -> Maybe (Quotient a)
quotient n d = case d of
  0 -> Nothing
  _ -> let g = gcd n d in Just (Q (quot (n * signum d) g) (quot (abs d) g))

unsafeQuotient :: (Stack.HasCallStack, Integral a) => a -> a -> Quotient a
unsafeQuotient n d = case quotient n d of
  Nothing -> error "Quotient has zero denominator"
  Just q -> q

(%) :: Integral a => a -> a -> Quotient a
(%) = unsafeQuotient
infixl 7 %

numerator :: Quotient a -> a
numerator (Q n _) = n

denominator :: Quotient a -> a
denominator (Q _ d) = d

fromRatio :: Ratio.Ratio a -> Quotient a
fromRatio r = Q (Ratio.numerator r) (Ratio.denominator r)

toRatio :: Integral a => Quotient a -> Ratio.Ratio a
toRatio (Q n r) = n Ratio.% r

instance (Num a, Ord a) => Ord (Quotient a) where
  compare (Q a b) (Q c d) = compare (a * d) (b * c)

instance Integral a => Num (Quotient a) where
  Q a b + Q c d = unsafeQuotient ((a * d) + (b * c)) (b * d)
  Q a b - Q c d = unsafeQuotient ((a * d) - (b * c)) (b * d)
  Q a b * Q c d = unsafeQuotient (a * c) (b * d)
  abs (Q n d) = Q (abs n) d
  fromInteger n = Q (integerToNum n) 1
  negate (Q n d) = Q (negate n) d
  signum (Q n _) = Q (signum n) 1

instance Integral a => Real (Quotient a) where
  toRational (Q n d) = integralToInteger n Ratio.% integralToInteger d

instance Integral a => Enum (Quotient a) where
  enumFrom q = enumFromThen q (succ q)
  enumFromThen q p = let s = p - q in iterate (+ s) q
  enumFromThenTo q1 q2 p =
    let f = if q2 < q1 then (>= p) else (<= p)
    in takeWhile f (enumFromThen q1 q2)
  enumFromTo q p = enumFromThenTo q (succ q) p
  fromEnum = integerToInt . truncate
  pred = (subtract 1)
  succ = (+ 1)
  toEnum n = Q (intToIntegral n) 1

instance Integral a => Fractional (Quotient a) where
  Q a b / Q c d = unsafeQuotient (a * d) (b * c)
  fromRational r = Q
    (integerToIntegral (Ratio.numerator r))
    (integerToIntegral (Ratio.denominator r))
  recip (Q n d) = unsafeQuotient d n

instance Integral a => RealFrac (Quotient a) where
  properFraction (Q n d) = let (q, r) = quotRem n d in (fromIntegral q, Q r d)
  round q = let (n, f) = properFraction q in
    case (compare (abs f) 0.5, odd n) of
      (LT, _) -> n
      (EQ, False) -> n
      (EQ, True) -> n + signum n
      (GT, _) -> n + signum n

integerToNum :: Num a => Integer -> a
integerToNum = fromInteger

integralToInteger :: Integral a => a -> Integer
integralToInteger = toInteger

intToIntegral :: Integral a => Int -> a
intToIntegral = fromIntegral

integerToIntegral :: Integral a => Integer -> a
integerToIntegral = fromInteger

integerToInt :: Integer -> Int
integerToInt = fromInteger