CODEWITHSUNDEEP
haskell
Kevin Meredith
Kevin Meredith

Reputation: 41919

Defining 'empty' on Heap Typeclass

I'm trying to copy the ML code from Purely Functional Data Structures into Haskell.

class (Ord a) => Heap a where
    empty :: Heap a
    ...

But I get this compile-time error:

Prelude> :l Heap.hs 
[1 of 1] Compiling Main             ( Heap.hs, interpreted )

Heap.hs:2:18:
    Expected kind ‘*’, but ‘Heap a’ has kind ‘Constraint’
    In the type ‘Heap a’
    In the class declaration for ‘Heap’

It seems appropriate to me that empty should be a function in the Heap type-class.

What am I doing wrong?

Upvotes: 0

Views: 116

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477180

Type-classes in Haskell are not (that much) related to classes in Object-oriented program. To put it simple: a type-class groups a set of data instances that support a set of functions.

You thus define a class as

class Foo a where
    bar :: a -> Bool
    qux :: a

That doesn't mean Foo is a type, it means that for any datastructure a, that is an instance of Foo, you should implement these methods.

In that sense it's more an interface, types itself are instances of a class.

Now you can for instance define a datastructure, for instance a "naive" map approach:

data ListMap a b = ListMap [(a,b)]

Now that means that every map is stored as a list of (a,b) tuples with the ListMap "constructor".

You can then for instance define an empty method for such listmap:

empty :: ListMap a b
empty = ListMap []

It thus means that you create a ListMap with an empty list.

It can however be useful to construct a class in case you are planning to implement multiple datastructures that behave like a map. In that case you can for instance define:

class Map a where
    empty :: a

Now you can make ListMap an instance of Map with:

instance Map (ListMap a b) where
    empty = ListMap []

Later, if you want to define functions that make returns for instance the list of keys, etc. you can define multi-parameter type classes.

Thus to answer your question in short: if you use a class, the empty method has the signature a, but you should first define a datastructure, a class is more what objected oriented programming languages call an "interface".

Upvotes: 3

Related Questions