Don't understand this collection class syntax

January 30, 2023

class Collection c where
  empty :: c key value
  singleton :: key -> value -> c key value
  insert
    :: Ord key
    => key -> value -> c key value -> c key value
  lookup :: Ord key => key -> c key value -> Maybe value
  delete :: Ord key => key -> c key value -> c key value
  keys :: c key value -> [key]
  values :: c key value -> [value]
  toList :: c key value -> [(key, value)]
  fromList :: Ord key => [(key,value)] -> c key value

This is unlike what I’ve read about typeclasses, or the syntax I’m used to. I don’t understand what c key value represents. Also, what is empty supposed to be? It doesn’t resemble a function. Appreciate and am thankful for any help, I’m new to haskell and this is confusing for me

>Solution :

The type parameter c will here not unify with a "concrete" type, but with a type constructor that still expects two parameters.

A simple collection could be:

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

then we define an instance of Collection with:

instance Collection ListMap where
    empty = ListMap []

    -- …

Indeed, empty here has as type c key value, so ListMap key value, which is then a concrete type.

In this case, a function like fromList :: Ord key => [(key,value)] -> c key value will thus result in fromList :: Ord key => [(key,value)] -> ListMap key value.