Haskell中如何维护Range类型下界≤上界的类型不变式？

问题背景 #

我尝试用如下代码建模泛型Range类型：

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

为避免使用者意外创建lower大于upper的Range，我添加了智能构造器（仅导出它而非数据构造器）：

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

之后我为其实现了Functor实例：

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

但这会导致问题，比如执行以下代码后，r2的upper会小于lower：

main :: IO ()
main = do
  let r1 = range 1 2
      r2 = fmap negate r1
  return ()
  -- 此时r2的upper小于lower

我尝试在fmap实现中使用智能构造器range：

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

但由于f lower和f upper所在的类型没有Ord约束，代码无法编译。请问如何修复以维护lower始终≤upper的类型不变式？

解决方案 #

方法1：改用Contravariant逆变函子（推荐） #

当映射函数可能反转值的顺序（比如negate）时，Range的语义更适合对应逆变函子（Contravariant Functor）。逆变函子的contramap方法会反向处理输入，刚好能维护lower ≤ upper的约束：

首先导入Contravariant模块：

import Data.Functor.Contravariant

然后实现Contravariant实例：

instance Contravariant Range where
  contramap f (Range l u) = range (f u) (f l)

此时调用contramap negate (range 1 2)会得到range (-2) (-1)，自动保证了lower ≤ upper的不变式。

方法2：自定义带Ord约束的函子类 #

如果坚持要使用协变映射的语义，可以放弃标准Functor，自定义一个带Ord约束的函子类：

class OrdFunctor f where
  ofmap :: (Ord a, Ord b) => (a -> b) -> f a -> f b

为Range实现这个类：

instance OrdFunctor Range where
  ofmap f (Range l u) = range (f l) (f u)

这种方式可以直接复用智能构造器维护约束，代价是无法使用标准Functor生态的工具函数。

方法3：限制映射函数为单调递增类型 #

可以定义一个描述单调递增函数的类型类，约束fmap的输入函数必须满足单调性：

class Ord a => MonotonicFunc f a where
  applyMono :: f -> a -> a
  -- 隐含约束：若x ≤ y，则applyMono f x ≤ applyMono f y

修改fmap实现并添加约束：

instance Functor Range where
  fmap :: MonotonicFunc f a => f -> Range a -> Range a
  fmap f (Range l u) = Range (applyMono f l) (applyMono f u)

这种方式需要为所有用到的单调函数实现MonotonicFunc实例，灵活性较低，适合特定场景。

方法4：动态检查（不推荐） #

可以借助ScopedTypeVariables扩展，给Functor实例添加Ord a约束并动态比较映射后的值，但这会违反标准Functor的定律（比如fmap id可能修改Range结构），且兼容性差：

{-# LANGUAGE ScopedTypeVariables #-}

instance Ord a => Functor Range where
  fmap f (Range l u) = case compare (f l) (f u) of
    LT -> Range (f l) (f u)
    _  -> Range (f u) (f l)

总结 #

最贴合Range语义的方案是使用Contravariant逆变函子；若需要协变映射，自定义带Ord约束的函子类是更严谨的选择。

内容的提问来源于stack exchange，提问作者rexcfnghk