I was messing around with type-classes (familiarization exercises) when
I hit a probably newbie problem. Reducing it to the simplest case...
module BinTree ( WalkableBinTree, BT (Branch, Empty) ) where
-- n : node type
-- d : data item type wrapped in each node
class WalkableBinTree n where
wbtChildren :: n -> Maybe (n, n)
wbtData :: n -> Maybe d
-- Simple tree type, mostly for testing
data BT x = Branch x (BT x) (BT x)
| Empty
instance WalkableBinTree (BT x) where
wbtChildren (Branch d l r) = Just (l, r)
wbtChildren Empty = Nothing
wbtData (Branch d l r) = Just d
wbtData Empty = Nothing
Loading this code into GHCi, I get...
Prelude> :load BinTree
[1 of 1] Compiling BinTree ( BinTree.hs, interpreted )
BinTree.hs:16:39:
Couldn't match type `x' with `d'
`x' is a rigid type variable bound by
the instance declaration at BinTree.hs:12:32
`d' is a rigid type variable bound by
the type signature for wbtData :: BT x -> Maybe d
at BinTree.hs:16:5
In the first argument of `Just', namely `d'
In the expression: Just d
In an equation for `wbtData': wbtData (Branch d l r) = Just d
Failed, modules loaded: none.
Prelude>
I've tried varying a number of details. Adding another parameter to the
type-class (for the item-data type) requires an extension, and even then
the instance is rejected because (I think) the tree-node and item-data
types aren't independent.
In any case, I can't understand why those types can't match.