红黑树的Haskell算者

Question

所以我正在学习Haskell,我有一个红黑树,红色和黑色节点的类型不同,实现如下:

data Rbtree a1 b1 = EmptyTree | Node a1 (Rbtree b1 a1) (Rbtree b1 a1) deriving (Show, Read, Eq)

现在我需要为它定义一个仿函数实例.因为Rbtree是一个类型构造函数,它需要两个参数来创建一个实例Rbtree c.在此之后我被困住了.我的代码现在是这样的:

instance Functor (Rbtree c) where
fmap f EmptyTree = EmptyTree
fmap f (Node x left right) = Node x (fmap f left) (fmap f right)

正如你猜测的那样,不能编译.(编译错误).我明白,fmap因为它必须是(a -> b) -> (Rbtree c) a -> (Rbtree c) b并且必须更深入地寻找Node它所必需的部分(a -> b) -> (Node c (Rbtree a c) (Rbree a c)) -> (Node c (Rbtree b c) (Rbree b c)).我不明白的是如何展开left,right所以我只能申请其中的f一部分.我想我在这里遗漏了一些东西.

Answer 1

你可以这样做Rbtree一个Bifunctor(见bifunctors包):

import Data.Bifunctor

data Rbtree a1 b1 = EmptyTree | Node a1 (Rbtree b1 a1) (Rbtree b1 a1)

instance Bifunctor Rbtree where
  bimap _ _ EmptyTree = EmptyTree
  bimap f g (Node x l r) = Node (f x) (bimap g f l) (bimap g f r)

在这个实例中,您现在拥有两个first和second函数来映射红色或黑色节点(second〜fmap).实际上你可以Functor像这样定义实例:

instance Functor (Rbtree c) where
  fmap = second

例

>>> let t = Node 1 (Node "hello" EmptyTree EmptyTree) EmptyTree
>>> bimap show length t
Node "1" (Node 5 EmptyTree EmptyTree) EmptyTree
>>> fmap length t
Node 1 (Node 5 EmptyTree EmptyTree) EmptyTree
>>> first show t
Node "1" (Node "hello" EmptyTree EmptyTree) EmptyTree