Haskell Datatypes with unknown types

Question

For an assignment, the following codes was given

-- 2. Index

class Index i where
  findEntry :: Eq k => k -> i k -> Maybe Entry
  empty     :: Eq k => i k
  singleton :: Eq k => k -> Entry -> i k
  (<+>)     :: Eq k => i k -> i k -> i k

-- a. Complete the definition of Assoc
data Assoc k
  = MkAssoc [(k,Entry)]
  deriving (Eq,Show)

-- b. Complete the instance of Index for Assoc
instance Index Assoc where

I'm now completely stuck at question 2.b. How do I make the empty and findEntry and the other things? Where does the 'k' come from in index? How come the output of some functions is (i k)? That't not even a type.

Answer 1

The i in class Index i stands for a type constructor of kind * -> *. That is, i can be something like Maybe, [], IO. More to the point i can also be Assoc.

Note that i on its own is not a type, but a type constructor, like Assoc on its own is not a type. Instead i k is a type like Assoc k is a type.

The instance you need to write has the following methods to be defined:

instance Index Assoc where
  findEntry :: Eq k => k -> Assoc k -> Maybe Entry
  empty     :: Eq k => Assoc k
  singleton :: Eq k => k -> Entry -> Assoc k
  (<+>)     :: Eq k => Assoc k -> Assoc k -> Assoc k

You should now be able to fill in the actual definitions.