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

consider following definition binary trees:

data tree = nil | node (tree a) (tree a) 

the foldable instance can defined follows:

instance foldable tree   foldr _ z nil = z   foldr f z (node l d r) = foldr f (f d (foldr f z l)) r 

but problem elem function runs in o(n) rather o(log n). when try implement 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 could not deduce (ord a) arising use of ‘<’. how can problem fixed?

you cannot use elem method foldable class, since foldable api requires elem implementation of instances able search elements of type eq instance. "an elem polymorphic eq" intentional choice in design of foldable typeclass.

your elem function, while useful, not compatible elem method foldable typeclass, since not generic enough typeclass's desires. best way export elem function type define separate function outside of typeclass.