multiple type parameters in haskell type classes

Question

I'm trying to do some abstraction in Haskell98 but doen't know how to do it.

What I want to do is to define a class for types that may be converted into lists.

toList :: a -> [b]

But I don't know how to define a class for this method. I brought up the following three ideas:

class ToList a b where
    toList :: a -> [b]

class ToList a where
    toList :: a -> [b]

class ToList a where
    toList :: a b -> [b]

The first one doesn't work because Haskell98 doesn't allow multiple parameter classes.

The second one doesn't work because b depends on a and can't be implemented for every b.

The third doesn't work either because I don't know how to instanciate the class with a type where 'b' isn't the last type-parameter.

data HTree a b = Nil | Node a b (HTree a b) (HTree a b)

toList Nil = []
toList Node x y l r = toList l ++ [(x,y)] ++ toList r

or

toList Nil = []
toList Node x y l r = toList l ++ [x] ++ toList r

How would I do something like that?

Answer 1

I'd recommend Type classes are not as useful as they first seem - if the putative class has just one interface method, consider declaring a function type instead. I came from an OO background too and found I spent far too much time trying to make "class" mean what I thought it meant, when really I should have been using "data".

It is much easier just to write your toList' function and then 'lift' it to operate on your data structure. In fact, the acclaimed Yet Another Haskell Tutorial goes through an extensive exercise showing how it's done, and uses a binary tree as the example. The great thing about doing a lift is it distinguishes what is important - the structure of the datatype, not the implementation of toList' - so once the lift is done to perform 'in order traversal of the datatype', you can use the lift to do anything - toList, print, whatever. Supporting toList isn't the important part of the data structure, so it shouldn't be in a class declaration - the important part is how to traverse the data structure.

Answer 2

You probably want to choose the last option for class ToList, and make (HTree a) instance of ToList. Then toList has type (HTree a b) -> [b], not for example (HTree a b) -> [(a,b)]. I assume you are thinking a as "key" and b as "value" type.

class ToList a where
    toList :: a b -> [b]

data HTree a b = Nil | Node a b (HTree a b) (HTree a b)

instance ToList (HTree a) where
    toList Nil = []
    toList (Node x y l r) = toList l ++ [y] ++ toList r

test = toList (Node "a" 1 (Node "b" 2 Nil Nil) Nil)
-- test == [2,1]

Answer 3

See also Data.Foldable in the standard library, which provides a toList function for any Foldable instance. Foldable takes a bit of sophistication to instantiate, but it would be good practice. As a bonus, your HTree type is almost exactly the same as the example instance in the documentation.

Additionally, I recommend changing your HTree to:

data HTree a = Nil | Node a (HTree a) (HTree a)

And then using HTree (a,b) instead of HTree a b. This single-parameter version will be more easily composable with standard types and instances, and it gets more to the point of what is going on since it depends on both parameters in the same way. It is also a Functor, and defining such an instance will make this type really nice to work with.