是否可以在Haskell中为已排序的二叉树树创建Functor实例？

不,没有办法用Functor类型类做到这一点.如你所说,前奏给了我们 ¹

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

它没有提供任何方法来限制b.我们可以定义一个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

(通常,你会看到关于受限制的monad的东西;它是相同的想法.)

或者,正如jozefg建议的那样,您可以编写自己的treeMap函数,而不是将其放在类型类中.没有错.

但是请注意,制作SortBinTree仿函数时要小心; 以下不是 fmap.(但是,它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),这可能违反了你的不变量 - 它向后排序.2所以要确保你fmap的保持不变. Data.Set将这些拆分为map,这可以确保不变量被保留,并且mapMonotonic需要您传递一个保持顺序的函数.后一个函数具有简单的实现,如果给出不合作的函数notFmap,则可能产生无效的Sets.

¹ 该Data.Functor模块还公开了(<$) :: Functor f => a -> f b -> a类型类方法,但只是在那种情况下fmap . const具有更快的实现.

²但是,notFmap 是 fmap从子类Hask其对象是与类型的Ord实例,并且其态射是保序映射到的子类别Hask其对象是SortBinTree结束了类型的一个Ord实例.(模数一些关于"不合作" Eq/ Ord实例的潜在担忧,比如那些捣乱Set的人Functor.)

有两种选择,如果你的类型满足仿函数法则那么正确的技巧就是

{-# 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谈论的那个.