Custom Functor instance: Expected kind ‘* -> *’, but ‘AST’ has kind ‘*’

Question

I have this rather simple ADT:

data AST = Node String [AST]
     | Leaf String
     | Empty
    deriving (Show)

and this Functor instance:

instance Functor AST where
    fmap f (Node s l) = Node (f s) (fmap f l)
    fmap f (Leaf s)   = Leaf (f s)
    fmap f Empty      = Empty

But when I try to compile it I get this error that I absolutely not understand:

Expected kind ‘* -> *’, but ‘AST’ has kind ‘*’
   • In the first argument of ‘Functor’, namely ‘AST’
     In the instance declaration for ‘Functor AST’

Does anyone know why this happens? I can't find a solution in the Internet.

Answer 1

A functor works on type constructors: if you give it an AST, it expects to see a:

data AST a = ...
--       ^ type parameter

We can also see this in the definition of the Functor class:

class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b

Notice that the f in the head of the class has "kind" * -> * this means that acts as some sort of function that takes another type (the first *) and produces a type (the second *). As you can see fmap will take a function of type a -> b (where we have not much control over what b is). In your definition of fmap, we could only provide a String -> String function.

Right now it does not make much sense to make AST a functor, since it is not a functor.

You can however easily generalize your AST into:

data AST a = Node a [AST a]
     | Leaf a
     | Empty
    deriving (Show)

If you work with that type, an AST String is equivalent to your old definition for an AST.

The same holds for a list [] (which is a Functor as well). A pseudo-definition of a list is:

data [] a = [] | a : [a]

We define Functor over a list as:

instance Functor [] where
    fmap _ [] = []
    fmap f (x:xs) = (f x) : (fmap f xs)

Mind that we did not state Functor [a], but Functor [].