Don't understand this collection class syntax-CodePudding

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

CodePudding user response：

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.

CodePudding user response：

You can infer from how key and value are used that they must be types (things of kind *). Thus, from how c is used, you can infer that it must be something of kind * -> * -> *: it gets applied to two types to produce another type.

With the KindSignatures extension, we can make this more explicit. You could write

{-# LANGUAGE KindSignatures #-}

class Collection (c :: * -> * -> *) where
    empty :: c key value
    -- etc.