On 06/01/2012 10:29, Steffen Schuldenzucker wrote:
On 01/06/2012 11:16 AM, Steve Horne wrote:
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
With 'd' not being mentioned anywhere, the signature of wbtData means
"forall d. n -> Maybe d". In particular, wbtData == const Nothing.
I'm not sure what to make of that. Even if the result of wbtData is
always Nothing, surely it still has a static type?
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.
Did you try something like
> {-# LANGUAGE MultiParamTypeClasses #-}
> class WalkableBinTree n d where
> ... (same code as above, but 'd' is bound now)
> ...
> instance WalkableBinTree (BT x) x where
> ...
Precisely that. In that case, I get...
C:\_SVN\dev_trunk\haskell\examples>ghci -XMultiParamTypeClasses
GHCi, version 7.0.4: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> :load BinTree
[1 of 1] Compiling BinTree ( BinTree.hs, interpreted )
BinTree.hs:12:12:
Illegal instance declaration for `WalkableBinTree (BT x) x'
(All instance types must be of the form (T a1 ... an)
where a1 ... an are *distinct type variables*,
and each type variable appears at most once in the instance head.
Use -XFlexibleInstances if you want to disable this.)
In the instance declaration for `WalkableBinTree (BT x) x'
Failed, modules loaded: none.
Prelude>
If I specify both extensions (-XMultiParamTypeClasses and
-XFlexibleInstances) it seems to work, but needing two language
extensions is a pretty strong hint that I'm doing it the wrong way.
The goal is fairly obvious - to have type-classes for binary tree
capabilities so that different implementations can support different
subsets of those capabilities. Being able to walk a binary tree doesn't
need ordering of keys, whereas searching does. A red-black tree needs
somewhere to store it's colour in the node, yet the walking and
searching functions don't need to know about that.
As far as I remember, none of the tutorials I've read have done this
kind of thing - but it seemed an obvious thing to do. Obviously in the
real world I should just use library containers, but this is about
learning Haskell better in case a similar problem arises that isn't
about binary trees.
How should I be handling this?
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
