A Foldable binary search tree
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?
Hi
data (Ord a) => BST a = Empty | BST (BST a) a (BST a)
Experience has taught me to _never_ put class contexts on data definitions. Now you can't write something as simple as "Empty" - you have to give it a class context. This is just plain annoying. I would accept this pain if it meant I could write: insert :: a -> BST a -> BST a and have the Ord silently inserted - but you can't. You still have to write the Ord a => explicitly. As a result, I see no advantage to adding the class constraint, and plenty of disadvantages. If there are some advantages to this context I would be interested to know what they are. Thanks Neil
On Sat, 22 Dec 2007 22:41:37 -0500, Neil Mitchell
Hi
data (Ord a) => BST a = Empty | BST (BST a) a (BST a)
Experience has taught me to _never_ put class contexts on data definitions. Now you can't write something as simple as "Empty" - you have to give it a class context. This is just plain annoying.
With the class context in the BST definition, ghc gives no complaints when I evaluate "Empty": *BST> Empty Empty *BST> :t Empty Empty :: BST a I assume I misunderstand you.
I would accept this pain if it meant I could write:
insert :: a -> BST a -> BST a
and have the Ord silently inserted - but you can't. You still have to write the Ord a => explicitly.
I see what you mean here. To get ghc to accept my code (where BST is Foldable), I omit the class context from the data definition, but add the Ord class context to the signatures of the BST functions that require it (insert, for example).
As a result, I see no advantage to adding the class constraint, and plenty of disadvantages. If there are some advantages to this context I would be interested to know what they are.
Thanks
Neil
Thanks! Brad
Hi Brad,
Experience has taught me to _never_ put class contexts on data definitions. Now you can't write something as simple as "Empty" - you have to give it a class context. This is just plain annoying.
With the class context in the BST definition, ghc gives no complaints when I evaluate "Empty":
In some circumstances, you need to give a type sig. For example using Hugs: Main> Empty ERROR - Cannot find "show" function for: *** Expression : Empty *** Of type : BST a I guess GHC has enough defaulting to display this anyway. You'll also have the dreaded-evil-horrid monomorhpism restriction if you type. empty = Empty Thanks Neil
On Sun, 23 Dec 2007 06:42:52 -0500, Neil Mitchell
Hi Brad,
Experience has taught me to _never_ put class contexts on data definitions. Now you can't write something as simple as "Empty" - you have to give it a class context. This is just plain annoying.
With the class context in the BST definition, ghc gives no complaints when I evaluate "Empty":
In some circumstances, you need to give a type sig. For example using Hugs:
Main> Empty ERROR - Cannot find "show" function for: *** Expression : Empty *** Of type : BST a
I guess GHC has enough defaulting to display this anyway.
Sorry, forgot to mention that my BST derives Show.
You'll also have the dreaded-evil-horrid monomorhpism restriction if you type.
empty = Empty
Thanks
Neil
More stuff for me to read about :-) Brad
| > data (Ord a) => BST a = Empty | BST (BST a) a (BST a) | | Experience has taught me to _never_ put class contexts on data | definitions. Correct. Haskell-98 contexts on data-type declarations are a mis-feature of Haskell, which I resisted at the time but failed to eliminate. As others have pointed out, GHC allows you to put a context on any data constructor. I prefer this "where" syntax: data BST a where Empty :: BST a BST :: Ord a => BST a -> a -> BST a -> BST a but the other (existential-like) syntax also works: data BST a = Empty | Ord a => BST (BST a) a (BST a) The constructors have the signature they advertise. When you use BST as a constructor, you must supply an Ord context. But when you pattern-match on it, you *get* an Ord context. For example f :: a -> BST a -> Bool f x Empty = False f x (BST t1 y t2) = x>y Note the absence of an Ord context on f. This works properly when combined with GADTs. The uniform rule is: you must supply the context when you use the constructor as a function, and you bring the context into scope when you pattern match on the constructor. Having this "context on data constructors" work right all the time is relatively new. Previously it really only worked for existentials; but now there are no restrictions on the contexts you write on data constructors. The Haskell 98 behaviour remains when you use the Haskell-98 syntax. | I would accept this pain if it meant I could write: | | insert :: a -> BST a -> BST a And so you can! But to get this, you'll have to write an Ord context on the Empty constructor too. Simon
Simon Peyton-Jones wrote:
As others have pointed out, GHC allows you to put a context on any data constructor. I prefer this "where" syntax:
But, in 6.8.x, you will need -XGADTS to permit this. 6.6.x permitted it anyway, arguably in error. http://hackage.haskell.org/trac/ghc/ticket/1901 Jules
participants (4)
-
Brad Larsen -
Jules Bean -
Neil Mitchell -
Simon Peyton-Jones