为二进制搜索树定义fmap

Question

我正在完成“Haskell开始”一书中的练习。练习4-8是使二叉树成为函式的一个实例，并定义fmap.这就是这棵树的样子：

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

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

两个问题：

1. 自fmap :: (a -> b) -> BinaryTree a -> BinaryTree b以来，我如何执行b也是序数？如果它不一定是函子，我可以简单地做fmapOrd :: (Ord a, Ord b) => (a -> b) -> BinaryTree a -> BinaryTree b，但是函子类型不强制执行Ord约束。
2. 高效的实现是什么样子的？我的第一个想法是折叠在树上，并根据映射的值建立一棵新的树。不幸的是，我没有走这么远，因为(1)。

Answer 1

Functor和fmap的要点是，它适用于可以存储在数据结构中的所有a和b，就像Monad也适用于所有类型的a一样。您的Functor实例应该如下所示

instance Functor BinaryTree where
    fmap f Leaf = Leaf
    fmap f (Node a l r) = Node (f a) (fmap f l) (fmap f r)

但是，如果要确保二叉树上的映射保持平衡，则需要一个函数。

balanceTree :: Ord a => BinaryTree a -> BinaryTree a

您应该能够通过一些googling很容易地实现这个函数，然后您可以定义一个专门的映射函数。

binMap :: (Ord a, Ord b) => (a -> b) -> BinaryTree a -> BinaryTree b
binMap f = balanceTree . fmap f

然后，您应该确保您和您的库的用户不会使用fmap (除非必要)，而应该使用binMap。

Answer 2

如果要强制排序，则不能将二叉树作为函子，因为--正如您所指出的--类型不匹配。但是，虽然树不能是键上的函子，但它可以是值的函子，只要每个值都有单独的类型参数。标准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)

它几乎总是与您的意图相匹配，只需记住让最后一个类型参数是您想要映射的参数。

Answer 3

我不打算说我推荐下面的内容，但是为了完整性，实际上可以定义这样一个函子。

Functor类型要求您可以将任何函数放入Functor中。这通常意味着很难确保需要类型实例的不变量。但是，我们可以在很大程度上控制这种情况，并最终得到一个Functor实例。实际上，这意味着我们可以使用类型系统来确保我们将我们的再平衡推迟到更方便的时间。

首先，我们将介绍对上述类型的需求。特别是，我们将给它一个维护平衡的Monoid实例。这很好，因为Monoid不要求容器是多态的。

instance Ord a => Monoid (BalancedTree a) where
  mempty = Leaf
  mappend Leaf Leaf = Leaf
  mappend Leaf b    = b
  mappend b    Leaf = b
  mappend (Node a l1 r1) (Node b l2 r2) = ... -- merge and rebalance here

现在，使用这个实例，我们可以编写几乎与Monad实例对应的BinaryTree函数。特别是，我们需要它来结合我们的新树作为构建使用bindBin，几乎版本的(>>=)上的二进制搜索树。

returnBin :: a -> BinaryTree a
returnBin a = Node a Leaf Leaf

bindBin :: Ord b => BinaryTree a -> (a -> BinaryTree b) -> BinaryTree b
bindBin Leaf _ = Leaf
bindBin (Node a l r) f = bindBin l f <> f a <> bindBin r f

然后我们介绍这种非常奇怪的类型(它需要RankNTypes扩展)

newtype FBinaryTree a = 
  FBinaryTree (forall r . Ord r => (a -> BinaryTree r) -> BinaryTree r)

考虑这个问题有很多种方法，但我们只需注意到，FBinaryTree a和BinaryTree a之间有一个同构，基本上是由returnBin和bindBin见证的。

toF :: BinaryTree a -> FBinaryTree a
toF bt = FBinaryTree (bindBin bt)

fromF :: Ord a => FBinaryTree a -> BinaryTree a
fromF (FBinaryTree k) = k returnBin

最后，由于FBinaryTree继承了Cont monad或Yoneda引理类型的一些属性，我们可以为FBinaryTree定义一个Functor实例！

instance Functor FBinaryTree where
  fmap f (FBinaryTree c) = FBinaryTree (\k -> c (k . f))

因此，现在我们所要做的就是将我们的BinaryTree转换成FBinaryTree，在那里执行Functor操作，然后根据需要返回到BinaryTree。一帆风顺，对吧？

好吧，差不多了。事实证明，我们为此付出了巨大的效率代价。特别是，在使用像FBinaryTree这样的类型时，很容易出现指数膨胀。我们可以通过不时地通过FBinaryTree通过BinaryTree发送

optimize :: Ord a => FBinaryTree a -> FBinaryTree a
optimize = toF . fromF

正如类型所示，它要求我们在那里有一个Ord实例。实际上，代码将在那里使用Ord实例来执行所需的再平衡。