违反Haskell中的Functor规则的示例

Question

我有一个用于二叉树的数据结构和一个在其上的函子

data BST a = Empty | Node (BST a) a (BST a)
instance Functor BST  where
  fmap f Empty = Empty
  fmap f (Node l val r) = (Node (fmap f l) (f val  ) (fmap f r))

我需要找到一些BST实例和函数f的例子，其中Functor（Identity，composition）的规则是violated] >>

有人可以指出我正确的方向吗？

谢谢！

我有一个用于二叉树的数据结构，并且对它有一个函子BST a =空|节点（BST a）一个（BST a）实例函子BST，其中fmap f空=空fmap f（节点l val r）=（节点（fmap f l）...

Answer 1

您将找不到任何示例，因为您的定义包含了函子定律。您可以通过对树的深度进行归纳来证明这一点。基本案例是0深度树（即Empty），然后是Node案例的证明。证明很长但是很简单。