在Haskell中实现二叉树的O(log ) Foldable.elem

Question

考虑以下二叉树的定义：

data Tree a = Nil | Node (Tree a) a (Tree a)

Foldable实例的定义如下：

instance Foldable Tree where
  foldr _ z Nil = z
  foldr f z (Node l d r) = foldr f (f d (foldr f z l)) r

但问题是elem函数在O(n)中运行，而不是在O(log n)中运行。当我尝试实现自定义elem时

elem x Nil = False
elem x (Node l d r)
  | x == d = True
  | x < d = elem x l
  | otherwise = elem x r

我得到了Could not deduce (Ord a) arising from a use of ‘<’。如何解决此问题？

Answer 1

您不能将此elem方法用于Foldable类，因为Foldable要求其所有实例的elem实现能够搜索任何类型的元素，其中只有一个Eq实例。“一个对所有Eq都是多态的elem”是在设计Foldable类型类时有意选择的。

您的elem函数虽然非常有用，但与Foldable类型类的elem方法不兼容，因为它不够通用，不能满足类型类的需要。为您的类型导出elem函数的最好方法是在类型类之外定义一个单独的函数。