[Haskell-cafe] A Foldable binary search tree

Brad Larsen brad.larsen at gmail.com
Sat Dec 22 22:16:42 EST 2007

Mainly for pedagogical purposes, I'm writing a BST.  The elements in a BST  
need to be ordered, so I define the new data type like this:

data (Ord a) => BST a = Empty | BST (BST a) a (BST a)

After some hacking and some reading, I came across Data.Foldable, and  
think it would be neat to make BST Foldable:

instance Foldable BST where
   foldr f s Empty = s
   foldr f s (BST l v r) = foldr f (f v (foldr f s r)) l

However, ghc tells me ``Could not deduce (Ord a) from the context  
(Foldable BST) arising from use of `BST' at bst.hs:19:13-21'', which is  
the second line of the foldr definition.

If I remove the (Ord a) context from the BST data definition, ghc accepts  
my code.  However, I'd like to keep that context.  How does one do this?   

Brad Larsen

P.S.  Does that definition of foldr look reasonable, i.e. is it  
associating in the ``right'' order for a binary tree?

More information about the Haskell-Cafe mailing list