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

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?

+5
source share
1 answer

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

Your elem function, although very useful, is incompatible with the elem method for the Foldable class, since it is not universal enough for style desires. The best way to export an elem function for your type is to define a separate function outside the class.

+4
source

Source: https://habr.com/ru/post/1270296/


All Articles