[Haskell-cafe] What are Kind errors and how do you fix them?

[Carl Witty]

On Fri, 2004-03-26 at 20:08, S. Alexander Jacobson wrote:
> Ok, I am still trying to understand kind errors
> and now have a very simple class and types:
> 
>    class MyClass a b where emptyVal::a b
> 
>    type MyType a = [a]
>    type MyType2 = []

Let me rename some type variables here:

  class MyClass c d where emptyVal::c d

  type MyType a = [a]
  type MyType2 = []

> I can't figure out why some instance work and
> others don't.  e.g. this one works:
> 
>    instance MyClass MyType2 a where emptyVal=[]
> 
> But this one doesn't:
> 
>    instance MyClass (MyType a) a where emptyVal=[]

  instance MyClass (MyType b) b where emptyVal=[]

Here, you are matching the class declaration (MyClass c d) against the
instance declaration (MyClass (MyType b) b); this matches with
  c == MyType b
  d == b
Then you claim that emptyVal=[] has type (c d), which is type
(MyType b b); so you are using MyType as a type constructor with two
type arguments.  But MyType only takes one type argument, so this is an
illegal type.

> and neither does this one:
> 
>    instance MyClass (MyType) a where emptyVal=[]

This is a different problem.  Here, you have defined a type synonym
MyType which takes one argument, but you have not provided it any
arguments.  Type synonyms cannot be used this way; they are sort of like
macros, and the first step is macroexpansion -- so you are trying to use
a macro without providing the necessary arguments.

<technical note>
There are good technical reasons for the requirement that type synonyms
must always be fully applied.  Here's just one example of the sort of
trouble you run into without this requirement:

Suppose you have a function
  f :: a Int -> a Float

And suppose you have type synonyms:
  type Pairii a = (Int, Int)
  type Pairia a = (Int, a)
  type Pairaa a = (a, a)

What is the type of (f (3::Int,3::Int))?  Well, (3::Int,3::Int) has type
(Int,Int); this is the same as Pairii Int, so the result has type Pairii
Float which is (Int,Int).  But (Int,Int) is also the same as Pairia Int,
so the result has type Pairia Float which is (Int,Float); and (Int,Int)
is Pairaa Int, so the result has type Pairaa Float which is
(Float,Float).

Haskell avoids this dilemma by not treating Pairii, Pairia, and Pairaa
as first-class type constructors, so they can't match a in (a Int).  

By the way: the 2-tuple type constructor, (,), is a first-class type
constructor; so the type (Int,Int) is the same as (((,) Int) Int); this
matches (a Int) with a being ((,) Int), so the result type of the above
expression is ((,) Int Float) or (Int,Float).
</technical note>

> How do I make (MyType a) work?  For example, a
> real world example is:
> 
>    type MyType a = FiniteMap a String?

I hope you understand the kind error, and why (MyType a) is not what you
want.  To get an instance for MyClass MyType a, you'll need to make
MyType a first-class type constructor.  You can get first-class type
constructors with newtype (at the cost of having a constructor for the
type); the following works:

  newtype MyType a = Make_MyType [a]

  instance MyClass MyType a where emptyVal=Make_MyType []

Carl Witty