是否可以在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.

这里有标准的解决方法吗？任何fmap只为案例定义的方法b是在Ord类型类中？

Answer 1

不,没有办法用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.)

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