Consider the following definition for binary trees:
data Tree a = Nil | Node (Tree a) a (Tree a)
A Foldable instance can be defined as follows:
instance Foldable Tree where foldr _ z Nil = z foldr fz (Node ldr) = foldr f (fd (foldr fzl)) r
But the problem is that the elem function works in O(n) , not O(log n) . When I try to implement custom elem :
elem x Nil = False elem x (Node ldr) | x == d = True | x < d = elem xl | otherwise = elem xr
I get Could not deduce (Ord a) arising from a use of '<' . How can I fix this problem?
Hapal source share