A type that's easy to do arithmetic with and is guaranteed in bounds

Question

Bear with me... this problem takes some explaining, but I think it's an interesting problem, and I assume others have faced it.

I would like to have a type that I know will always have a value between 0 and 1, inclusive. That's easy enough to do, I can create a type UnitInterval and only expose my smart constructor, toUnitInterval and deconstructor fromUnitInterval.

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

-- | A number on the unit interval 0 to 1, inclusive.
newtype UnitInterval = UnitInterval Double
  deriving (Show, Eq, Ord, Fractional, Floating)

-- | Convert a value to a @UnitInterval@. The value will be capped to
--   the unit interval.
toUnitInterval :: Double -> UnitInterval
toUnitInterval = UnitInterval . max 0 . min 1

fromUnitInterval :: UnitInterval -> Double
fromUnitInterval (UnitInterval x) = x

So far so good. But users of my module will find that arithmetic with UnitIntervals and Doubles is messy. For example,

λ> let a = toUnitInterval 0.5
λ> let b = 0.25 :: Double
λ> toUnitInterval $ (fromUnitInterval a) * b
UnitInterval 0.125

Of course I could make UnitInterval a derived instance of Num, so I can easily do arithmetic as long as I stick to UnitIntervals.

λ> a*a
UnitInterval 0.25
λ> a+a+a
UnitInterval 1.5 -- Oops! out of range

But I could write a custom implementation of Num for UnitIntervals, where operations like + do bounds checking. But users of my module will need to do complex calculations where partial results won't be in range. So they'll have to convert everything to Doubles, do the calculation, and convert back to UnitIntervals at the end.

But wait... maybe there's a better way. I could make UnitInterval a functor! An expression like fmap (\x -> x * exp x) a should give the result UnitInterval 0.8243606353500641. Nice, clean code. Now, Functor has the kind (* → *), and UnitInterval has the kind *. But I can change that, like so...

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

-- | A number on the unit interval 0 to 1, inclusive.
newtype UnitInterval a = UnitInterval a
  deriving (Show, Eq, Ord, Num, Fractional, Floating)

-- | Convert a value to a @UnitInterval@. The value will be capped to
--   the unit interval.
toUnitInterval :: (Num a, Ord a) => a -> UnitInterval a
toUnitInterval = UnitInterval . max 0 . min 1

fromUnitInterval :: UnitInterval a -> a
fromUnitInterval (UnitInterval x) = x

instance Functor UnitInterval  where
  fmap f (UnitInterval x) = toUnitInterval (f x) -- line 16

But that doesn't compile. And in hindsight, I see that's because I would need to constrain the result of fmap, which would give it a different type signature than the one in Functor.

amy.hs:16:29:
    No instance for (Num b) arising from a use of ‘toUnitInterval’
    Possible fix:
      add (Num b) to the context of
        the type signature for
          fmap ∷ (a → b) → UnitInterval a → UnitInterval b
    In the expression: toUnitInterval (f x)
    In an equation for ‘fmap’:
        fmap f (UnitInterval x) = toUnitInterval (f x)
    In the instance declaration for ‘Functor UnitInterval’

Sigh... back to the first version, with ugly arithmetic. Does anyone have a better solution?

Answer 1

You're going to face some difficulty with what you ask because the numbers on [0, 1] are not closed under the (+) operation. In other words, the "within [0, 1]" guarantee is not preserved by addition.

So there are a few ways to interpret what you want. One is that you could be looking for "phases" of operation between each you re-constrain the values to lie on [0, 1]

mapConstrain :: (Num a, Ord a) => (a -> a) -> (UnitInterval a -> UnitInterval a)
mapConstrain f (UnitInterval val) = UnitInterval (max 0 (min 1 (f val)))

Having operations like this alone will be constraining you will find as it is difficult to write something like

a :: UnitInterval Double
b :: UnitInterval Double
a + b

using mapConstrain. The Applicative typeclass suggests a mechanism for lifting this issue, however.

Another way forward would be to do constraining after every operation. Then we could instantiate Num

newtype UnitInterval a = UI a

constrain :: (Num a, Ord a) => a -> a
constrain = max 0 . min 1

instance Num a => Num (UnitInterval a) where
  UI a + UI b = UI (constrain $ a + b)
  UI a * UI b = UI (constrain $ a * b) -- not technically needed!
  abs (UI a)  = UI a
  signum (UI a) = UI (signum a)
  ...

The final way forward is to allow for unbounded operations but only let users "view" UnitInterval values which are valid. This has perhaps the simplest implementation because you get to automatically derive Num

newtype UnitInterval a = UI a deriving Num

getUI :: (Num a, Ord a) => UnitInterval a -> Maybe a
getUI (UI a) = if (a <= 1 && a >= 0) then Just a else Nothing

Alternatively, you could just hit it with one final constrain. Of course, this mode of operation allows UnitInterval values to go outside of [0, 1] so long as they arrive back there before being viewed.

Answer 2

When I think about numbers between zero and one, I tend to think about one of two things:

Rational numbers

data SM = SM {diff :: Natural, den :: Natural}

toRatio :: SM -> Ratio Natural
toRatio (SM diff den) = (1 + den + diff) / (1 + den)

instance Eq SM where
  SM diffx denx == SM diffy deny =
     diffx * (deny + 1) == diffy * (denx + 1)

Such numbers are truly guaranteed to lie in the correct range.

Computable real numbers

These are much more horrible, but there's a package out there for them. Roughly speaking, you can represent numbers between 0 and 1 as infinite streams of bits. Implementing multiplication will be an interesting challenge; if you somehow manage to figure out division, you won't have to worry about division by zero because it will simply run forever.