Implement an O(log n) Foldable.elem for binary search trees in Haskell

Question

Consider the following definition for binary trees:

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

The Foldable instance can be defined as follows:

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

But the problem is that the elem function runs in O(n) rather than O(log n). When I try to implement a custom elem:

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

I get Could not deduce (Ord a) arising from a use of ‘<’. How can this problem be fixed?

Answer 1

You cannot use this elem method for the Foldable class, since the Foldable API requires the elem implementation for all of its instances to be able to search for any elements of any type with only an Eq instance. "An elem that is polymorphic for all Eq" was an intentional choice in the design of the Foldable typeclass.

Your elem function, while very useful, is not compatible with the elem method for the Foldable typeclass, since it is not generic enough for the typeclass's desires. The best way to export an elem function for your type would be to define a separate function outside of the typeclass.