[Haskell-cafe] A Foldable binary search tree
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?
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