design-patterns - 是否可以在 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 来做到这一点类型类。正如您所指出的，the Prelude gives us 1

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

如果我们有很多不同类型的Functor，这可能会变得烦人。 s( 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)的内容；这是相同的想法。)

或者，as jozefg suggested ，你可以自己写 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) ，这可能违反了你的不变量 - 它是向后排序的。²所以请确保你的 fmap是保持不变的。 Data.Set将它们分成 map , which makes sure the invariants are preserved,和 mapMonotonic , which requires you to pass in an order-preserving function 。后一个函数的实现很简单，如 notFmap ，但可能会产生无效的 Set s 如果给定不合作函数。

<小时/>

1 The Data.Functor module also exposes the (<$) :: Functor f => a -> f b -> a type class method ，但这只是以防万一 fmap . const实现速度更快。

² 但是，notFmap 是 fmap来自 Hask 的子类别，其对象是带有 Ord 的类型实例，其态射保序映射到 Hask 的子类别，其对象为 SortBinTree s 超过带有 Ord 的类型实例。 (对“不合作” Eq/Ord 实例的一些潜在担忧进行模数，例如那些与 Set 混淆的实例 Functor 。)