为二进制搜索树定义fmap
我正在完成“Haskell开始”一书中的练习。练习4-8是使二叉树成为函式的一个实例，并定义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也是序数？如果它不一定是函子，我可以简单地做fmapOrd :: (Ord a, Ord b) => (a -> b) -> BinaryTree a -> BinaryTree b，但是函子类型不强制执行Ord约束。 - 高效的实现是什么样子的？我的第一个想法是折叠在树上，并根据映射的值建立一棵新的树。不幸的是，我没有走这么远，因为(1)。
回答 5
Stack Overflow用户
发布于 2014-04-06 12:59:25
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。
Stack Overflow用户
发布于 2014-04-06 13:01:09
如果要强制排序，则不能将二叉树作为函子，因为--正如您所指出的--类型不匹配。但是，虽然树不能是键上的函子，但它可以是值的函子，只要每个值都有单独的类型参数。标准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)它几乎总是与您的意图相匹配，只需记住让最后一个类型参数是您想要映射的参数。
Stack Overflow用户
发布于 2014-04-06 18:34:07
我不打算说我推荐下面的内容，但是为了完整性，实际上可以定义这样一个函子。
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实例来执行所需的再平衡。
https://stackoverflow.com/questions/22899700
复制
相似问题
从playstore下载时签名的apk崩溃
获取崩溃签名的apk /bundle，但正常调试apk工作正常
下载apk时从google playstore获取邮件id
从playstore下载时应用程序崩溃
如何在playstore ApK上安装调试APK
领取专属 10元无门槛券
AI混元助手 在线答疑
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
