```{- |
This module provides efficient /half-integers/. That is,
normal integers and integers plus or minus 1/2. These are
sometimes useful for when a value can be an integer, or midway
between two integers.
-}

module Data.HalfInteger
(
HalfInteger (),
half, halve, double,
toHalfInteger, fromHalfInteger,
isInteger
)
where

{- |
The type of half-integers. The bounds are determined by the type
variable. For example, @HalfInteger Int@ has a range half as large
as @Int@ itself. (The @Bounded@ instance correctly reflects this.)
Note that @HalfInteger Integer@ is unbounded, like @Integer@
itself.

@HalfInteger@ values can be constructed as numeric literals
(e.g., @5 :: HalfInteger Int@), by conversions such as
@fromInteger@ or @fromIntegral@, or by several functions in this
module. Another common pattern is to write (say) @5 + half@ to
represent 5 1/2. Indeed, the @Show@ instance represents values
in this way.

Beware: The half-integers are /not/ closed under multiplication!
For example, @half * half@ should yield 1/4, which is not a valid
@HalfInteger@. (Currently it yields zero.) Addition and
subtraction, however, /are/ closed, and thus yield exact results.
-}
newtype HalfInteger i = HalfInteger i

{- |
Represents 1/2 as a @HalfInteger@. You can add this to integral
@HalfInteger@ values created in various ways to get the
half-part in.
-}
half :: (Integral i) => HalfInteger i
half = HalfInteger 1

{- |
Take an integer and halve its value, yielding a @HalfInteger@.
This conversion is always exact, and @halve . double == id@.
-}
halve :: (Integral i) => i -> HalfInteger i
halve = HalfInteger

{- |
Take a @HalfInteger@ and double its value, yielding a normal integer.
This conversion is always exact, and @double . halve == id@.
-}
double :: HalfInteger i -> i
double (HalfInteger x) = x

instance (Eq i) => Eq (HalfInteger i) where
(HalfInteger x) == (HalfInteger y) = x == y

instance (Ord i) => Ord (HalfInteger i) where
compare (HalfInteger x) (HalfInteger y) = compare x y

instance (Bounded i) => Bounded (HalfInteger i) where
minBound = HalfInteger minBound
maxBound = HalfInteger maxBound

instance (Integral i) => Show (HalfInteger i) where
showsPrec p (HalfInteger x) =
let
i = signum x * (abs x `div` 2)
s = if x < 0 then "-" else "+"
in
showParen (p > 6) \$
("fromInteger " ++) .
showsPrec 10 i .
if odd x then (" " ++ ) . (s ++) . (" half" ++) else id

instance (Integral i) => Num (HalfInteger i) where
(HalfInteger x) + (HalfInteger y) = HalfInteger (x + y)
(HalfInteger x) - (HalfInteger y) = HalfInteger (x - y)
(HalfInteger x) * (HalfInteger y) = HalfInteger (x * y `div` 2)
negate (HalfInteger x) = HalfInteger (    negate x)
abs    (HalfInteger x) = HalfInteger (    abs    x)
signum (HalfInteger x) = HalfInteger (2 * signum x)
fromInteger x = HalfInteger (2 * fromInteger x)

{- |
Convert any number into a @HalfInteger@. The rounding is somewhat
unpredictable, but any value exactly representable as a half integer
will be converted exactly.
-}
toHalfInteger :: (RealFrac x, Integral i) => x -> HalfInteger i
toHalfInteger x = HalfInteger (round \$ 2 * x)

{- |
Convert a @HalfInteger@ into some other kind of number.
This conversion is always exact.
-}
fromHalfInteger :: (Integral i, Fractional x) => HalfInteger i -> x
fromHalfInteger (HalfInteger x) = fromIntegral x / 2

{- |
Returns @True@ if this @HalfInteger@ can be exactly represented
as an ordinary integer, and @False@ if there is a half offset.
-}
isInteger :: (Integral i) => HalfInteger i -> Bool
isInteger (HalfInteger x) = even x
```