Creating instance of custom class-CodePudding

I seem to get an error message when trying to create an instance of IntegerGraph. I do not understand the error message. Any tips? Here's the code:

import Data.Map (Map)
import qualified Data.Map as Map
import Data.Set (Set)
import qualified Data.Set as Set


class IntGraph g where
  emptyG :: g
  ... (more constructors) 


type MyGraph n = (Map n (Set n))

instance IntGraph MyGraph where

Error message:

• Expecting one more argument to ‘MyGraph’ Expected a type, but ‘MyGraph’ has kind ‘* -> *’

• In the first argument of ‘IntGraph’, namely ‘MyGraph’ In the instance declaration for ‘IntGraph MyGraph

CodePudding user response：

In Haskell, just as term-level expressions have types, type-level expressions have "kinds". Type expressions that have kind *, like Bool, Int, Maybe [Char], and MyGraph Char represent types that have associated values of the type. For example, you can construct a MyGraph Char, like Map.fromList [('a', Set.fromList ['b','c'])] :: MyGraph Char, which is how we know MyGraph Char must be of kind *.

In constrast, type-level expressions that have kind * -> *, like MyGraph and Maybe have no associated values. There is no value of type Maybe, for example. Instead, these type-level expressions must first be "applied" to a type of kind * to produce another type-level expression of kind *, representing a type that can have values. For example, if we apply Maybe of kind * -> * to type [Char] of kind *, we get a new type Maybe [Char] of kind *.

If this is all new to you, you might find this old Computer Science Stack Exchange answer of mine helpful.

Anyway, your type class IntGraph can only have instances IntGraph g when g is a type expression of kind *. We can tell this is the case because your definition of class IntGraph g includes a method emptyG that returns a value of type g, meaning that g must be of kind *, the kind of type expressions representing types that have values.

When you try to define an instance instance IntGraph MyGraph, you are trying to define an instance for a type expression MyGraph of kind * -> *, and GHC doesn't like this. It tells you that in the expression instance IntGraph MyGraph, it was expecting MyGraph to be a "type" (technically, a type expression of kind *), but it instead discovered that MyGraph was of kind * -> *.

You can fix this by defining instances for specific MyGraphs:

instance IntGraph (MyGraph Char) where

or a single instance for all possible MyGraph as, but you do need to include that type variable a in the instance declaration, like so:

instance IntGraph (MyGraph a) where