是否可以在Haskell中为排序的二进制树创建一个Functor实例

Question

假设我们有一个SortBinTree类型的构造函数定义为，例如，

data SortBinTree a = EmptyNode | Node a (SortBinTree a) (SortBinTree a);

只有当a是Ord类型类的实例时，它才有意义，因此大多数函数在声明的开头都有:: (Ord a) =>，尤其是用于从列表创建此类树的函数。然而，为了教Haskell，SortBinTree是Functor类型类的一个实例，我们必须编写类似的东西

instance Functor SortBinTree where
  fmap g tree = ...

这里的问题是，我们必须处理g :: a->b，其中b不一定是Ord类型类的实例。这使得编写这样的函数成为问题，因为在创建SortBinTree b类型的元素时不能使用不等式。

这里有标准的解决方法吗？有没有办法只为b在Ord类型类中的情况定义fmap？

Answer 1

不，Functor类型的类无法做到这一点。正如您所指出的，前奏曲为我们提供了

class Functor f where
  fmap :: (a -> b) -> f a -> f b

这不提供在CCD_ 15上挂起限制的方式。我们可以定义一个OrdFunctor类：

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

如果我们有很多不同类型的Functors（EqFunctor、MonoidFunctor等），这可能会很烦人。但如果我们打开ConstraintKinds和TypeFamilies，我们可以将其推广到受限的函子类：

{-# LANGUAGE ConstraintKinds, TypeFamilies #-}
import GHC.Exts (Constraint)
import Data.Set (Set)
import qualified Data.Set as S
class RFunctor f where
  type RFunctorConstraint f :: * -> Constraint
  fmapR :: (RFunctorConstraint f a, RFunctorConstraint f b) => (a -> b) -> f a -> f b
-- Modulo the issues with unusual `Eq` and `Ord` instances, we might have
instance RFunctor Set where
  type RFunctorConstraint f = Ord
  fmapR = S.map

（通常，你会看到关于受限单子的东西；这是相同的想法。）

或者，正如jozefg所建议的，您可以只编写自己的treeMap函数，而不将其放在类型类中。这没什么错。

然而，请注意，当使SortBinTree成为函子时应该小心；以下是而不是CCD_ 24。（然而，这是deriving (..., Functor)将产生的，所以不要使用它。）

notFmap :: (Ord a, Ord b) => (a -> b) -> SortBinTree a -> SortBinTree b
notFmap f EmptyNode    = EmptyNode
notFmap f (Node x l r) = Node (f x) (notFmap l) (notFmap r)

为什么不呢？以notFmap negate (Node 2 (Node 1 EmptyNode EmptyNode) EmptyNode)为例。这将生成树Node (-2) (Node (-1) EmptyNode EmptyNode) EmptyNode)，这可能违反了不变量——它是向后排序的。²因此，请确保您的fmap是保持不变的。Data.Set将这些划分为map和mapMonotonic，前者确保不变量得到保留，后者要求传入一个保序函数。后一个函数的实现很简单，类似于notFmap，但如果给定不合作的函数，可能会产生无效的Set。

---

D.3 Data.Functor模块还公开了(<$) :: Functor f => a -> f b -> a类型的类方法，但这只是为了防止fmap . const有更快的实现。

²然而，notFmap是fmap，从对象是具有Ord实例的类型且态射是保序映射的Hask的子类别到对象是在具有Ord实例的类型上的SortBinTrees的Hask

Answer 2

有两种选择，如果你的类型满足函子定律，那么正确的技巧是

{-# LANGUAGE DeriveFunctor #-}
data SortBinTree a = EmptyNode
                   | Node a (SortBinTree a) (SortBinTree a)
                   deriving Functor
-- Or a manual instance if you have some invariants that
-- need additional jiggering.

并确保它的所有操作都需要一个Ord实例。如果有人决定让树处于无用状态，那么修复它就是他们自己的工作

然而，要使其工作，您必须满足函子定律

 fmap id         === id
 fmap f . fmap g === fmap (f . g)

因此，如果你从树中删除重复项，你就会遇到麻烦。这就是为什么Data.Set作为Functor的一个实例是可疑的，它违反了这个定律。

如果你违反了定律，那么你就不是函子。您不能向Haskell指定您只想处理Hask的子类别。在这种情况下，您应该只定义一个不同的功能

treeMap :: (Ord a, Ord b) => (a -> b) -> SortBinTree a -> SortBinTree b

在范畴论意义上，这仍然是一个函子，只是不是Functor所说的那个。