为二叉搜索树定义 fmap

Question

我正在完成“Beginning Haskell”一书中的练习。练习 4-8 将二叉搜索树作为 Functor 的实例并定义 fmap。这就是树的样子：

data BinaryTree a = Node a (BinaryTree a) (BinaryTree a) 
                  | Leaf
                    deriving Show

因为它是一棵搜索树，所以对树的所有操作都必须保持左子树中的所有值<节点的值，右子树中的所有值>节点的值的不变性。这意味着树中的所有值都必须是有序的 ( Ord a => BinaryTree a)。

两个问题：

因为fmap :: (a -> b) -> BinaryTree a -> BinaryTree b，我如何强制执行这b也是序数？如果它不必是 Functor，我可以简单地做fmapOrd :: (Ord a, Ord b) => (a -> b) -> BinaryTree a -> BinaryTree b，但 Functor 类型类不强制执行 Ord 约束。
一个有效的实施是什么样的？我的第一个想法是折叠树，并从映射的值中构建一棵新树。不幸的是，由于（1），我没有走到这一步。

Answer 1

如果你想强制排序，那么你的二叉树不能被做成函子，因为 - 正如你所指出的 - 类型不匹配。然而，虽然树不能是键上的函子，但它可以是值上的函子，前提是每个都有单独的类型参数。标准Data.Map（也实现为搜索树）以这种方式工作。

-- Now the "v" parameter can be mapped over without any care for tree invariants
data Tree k v = Node k v (Tree k v) (Tree k v) | Leaf

至于的实现fmap，你的第一个想法是对的。还有一种更懒的方法，即让 GHC 派生实例：

{-# LANGUAGE DeriveFunctor #-}

data Tree k v = Node k v (Tree k v) (Tree k v) | Leaf deriving (Functor)

它几乎总是符合您的意图，只需记住让最后一个类型参数成为您打算映射的参数。