[Haskell-cafe] A Foldable binary search tree

[Brad Larsen]

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?   
Thanks!


Brad Larsen

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