Frege: can I derive "Show" for a recursive type?

Question

I'm trying to implement the classical tree structure in frege, which works nicely as long as I don't use "derive":

data Tree a = Node a (Tree a) (Tree a)
            | Empty
derive Show Tree

gives me

realworld/chapter3/E_Recursive_Types.fr:7: kind error, 
type constructor `Tree` has kind *->*, expected was *

Is this not supported or do I have to declare it differently?

Answer 1

Welcome to the world of type kinds!

You must give the full type of the items you want to show. Tree is not a type (kind *), but something that needs a type parameter to become one (kind * -> *).

Try

derive Show (Tree a)

Note that this is shorthand for

derive Show (Show a => Tree a)

which resembles the fact that, to show a tree, you need to also know how to show the values in the tree (at least, the code generated by derive will need to know this - of course, one could write an instance manually that prints just the shape of the tree and so would not need it).

Generally, the kind needed in instances for every type class is fixed. The error message tells you that you need kind * for Show.

---

EDIT: eliminate another possible misconception

Note that this has nothing to do with your type being recursive. Let's take, for example, the definition of optional values:

data Maybe a = Nothing | Just a 

This type is not recursive, and yet we still cannot say:

derive Show Maybe   -- same kind error as above!!

But, given the following type class:

class ListSource c    -- things we can make a list from
    toList :: c a -> [a]

we need say:

instance ListSource Maybe where
    toList (Just x) = [x]
    toList Nothing  = []

(instanceand derive are equivalent for the sake of this discussion, both make instances, the difference being that derive generates the instance functions automatically for certain type classes.)

It is, admittedly, not obvious why it is this way in one case and differntly in the other. The key is, in every case the type of the class operation we want to use. For example, in class Show we have:

class Show s where
    show :: s -> String

Now, we see that the so called class type variable s (which represents any future instantiated type expression) appears on its own on the left of the function array. This, of course, indicates that s must be a plain type (kind *), because we pass a value to show and every value has per definition a type of kind *. We can have values of types Int or Maybe Int or Tree String, but no value ever has a type Maybe or Tree.

On the other hand, in the definition of ListSource, the class type variable c is applied to some other type variable a in the type of toList, which also appears as list element type. From the latter, we can conclude, that a has kind * (because list elements are values). We know, that the type to the left and to the right of a function arrow must have kind * also, since functions take and return values. Therefore, c a has kind *. Thus, c alone is something that, when applied to a type of kind * yields a type of kind *. This is written * -> *.

This means, in plain english, when we want to make an instance for ListSource we need the type constructor of some "container" type that is parameterized with another type. Tree and Maybe would be possible here, but not Int.