红黑树的 Haskell 仿函数

所以我正在学习 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)

你可以猜到它不能编译。 ( compilation errors )。我知道它的 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 应用于其中的一部分。我想我在这里遗漏了一些东西。

最佳答案

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

你对 RB 树的定义对我来说没有多大意义，但如果我遗漏了什么，这里有一个与其兼容的 Functor 实例。

关于红黑树的 Haskell 仿函数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23674139/