How can I maintain the type invariant of a Range type where the lower bound is always less than or equal to the upper bound

rexcfnghk 0
Viewed 95

I am trying to model a generic Range type with the following definition:

data Range a = Range
  { lower :: a
  , upper :: a }

I added a smart constructor (and only exported it without the data constructor) so that consumers cannot accidentally create a Range with its lower field larger than its upper field:

range :: Ord a => a -> a -> Range a
range lower upper =
  if lower > upper
  then Range upper lower
  else Range lower upper

This is all good and I moved on with deriving a Functor instance of it:

instance Functor Range where
  fmap f (Range lower upper) = Range (f lower) (f upper)

This became problematic because I can do:

main :: IO ()
main = do
  let r1 = range 1 2
      r2 = fmap negate r1
  return ()
  -- Now r2 has its upper field less than its lower field

My naive attempt would be to use the smart constructor range in the implementation of fmap like:

instance Functor Range where
  fmap f (Range lower upper) = range (f lower) (f upper)

However, this does not compile as f lower and f upper are not constrained to have an Ord a instance.

How can I fix this so I can maintain the type invariant of having lower always less than or equal to upper?

haskell
1 Answers

As mentioned in the comments, there's no way to make this a legal functor, because fmap f has to work for all functions f, even when the result type doesn't have an Ord instance.

As I see it, you have two good options:

First: don't define a functor constraint, make a new function rangeMap with a more restricted type (this is how set does it).

data Range a = Range { lower :: a, higher :: a } deriving Show

range :: Ord a => a -> a -> Range a
range lower upper =
  if lower > upper
  then Range upper lower
  else Range lower upper

rangeMap :: Ord b => (a -> b) -> Range a -> Range b
rangeMap f (Range x1 x2) = range (f x1) (f x2)

rangeMap (negate) $ range 2 1 
Range {lower = -2, higher = -1}

Second, change the representation of range so that it does support a Functor instance, but implement lower and higher as functions that require an Ord constraint.

data Range a = Range a a

instance Functor Range where
  fmap f (Range x1 x2) = Range (f x1) (f x2)

lower :: Ord a => Range a -> a
lower (Range x1 x2) = min x1 x2

higher :: Ord a => Range a -> a
higher (Range x1 x2) = max x1 x2

λ:r = negate <$> Range 1 2
λ:lower r
-2
λ:higher r
-1

Depending on your usecase, either one of these two approaches might be preferable.

userYQe60
Related