Errors from data type's Show instance

Question

I have been working through Gabriel Gonzale's excellent blog post on Free Monads. To assist my understanding I wanted to create a Show instance for the following type and play around with it in GHCi, the type (from the blog post) is:

data Thread m r = Atomic (m (Thread m r)) | Return r

And my Show instance is:

instance (Show m, Show r) => Show (Thread m r) where
  show (Atomic m x) = "Atomic " ++ show m ++ " " ++ show x
  show (Return x)   = "Return " ++ show x

Unfortunately GHCi gives me this error when trying to load the file:

• Expected kind ‘* -> *’, but ‘m’ has kind ‘*’
• In the first argument of ‘Thread’, namely ‘m’
  In the first argument of ‘Show’, namely ‘Thread m r’
  In the instance declaration for ‘Show (Thread m r)’

So, most importantly: what does this error mean, why am I getting it? I think answering that will help my understanding of the blog post immensely (albeit in a slightly roundabout way). Also, what would a working Show implementation look like? I tried looking at the instance for Either, but didn't understand what was going on.

Answer 1

According to Thread m r = Action (m (Thread m r) | …, m is something that takes a type and returns another type. We call m a type constructor or of kind * -> *. Another example for something like that is Maybe:

data Maybe a = Just a | Nothing

Maybe on it's own isn't a type. You have to provide it another type, e.g. Maybe Int or Maybe String.

Now Show expects a type with kind *. But Thread needs * -> *. Therefore, GHC gives up. Since Show m comes before Thread m r, GHC thinks its kind is *, which does not work for Action (m (Thread m r)), since that would need a type constructor (* -> *).

This problem, by the way, is why classes like Show1 exist in some packages. You could adopt that and then write your Show instance:

instance (Show1 m, Show r) => Show (Thread m r) where
  show (Atomic x) = "Atomic " ++ show1 x
  show (Return x) = "Return " ++ show x

Or you can delve into the realm of undecidable instances and say that Thread m r can be shown if m (Thread m r) can be shown:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}

instance (Show r, Show (m (Thread m r))) => Show (Thread m r) where
  show (Atomic x) = "Atomic " ++ show x
  show (Return x) = "Return " ++ show x

Answer 2

First of all, the error you receive is a kind error. A kind is the “type” of a type. Just as types classify values, kinds classify types. And just as Haskell infers types from values, it also infers kinds from types. We use the same symbol :: to denote that a value has a certain type (e.g., 1 :: Int) and to denote that a type has a certain kind (e.g., Int :: *).

There are two kinds mentioned in the error message: * is the kind of types that are inhabited by values, such as Int and Bool, while * -> * is the kind of type constructors such as Maybe, [], and IO. You can think of type constructors as type-level functions: Maybe takes a type (of kind *) as an argument and returns a type (also of kind *) as a result, e.g., Maybe Int :: *. Kinds are curried in the same way as functions; for example, Either has the kind * -> * -> * because it takes two arguments of kind * to produce a type of kind *:

Either :: * -> * -> *
Either Int :: * -> *
Either Int Bool :: *

So the error comes from the typeclass constraint on your Show instance:

instance (Show m, Show r) => Show (Thread m r) where
          ------

Show is the class of types of kind * that can be shown. You can see this by typing :kind Show (or :k Show) in GHCi:

> :kind Show
Show :: * -> Constraint

So Show takes a type of kind * and returns a typeclass constraint. Without getting into too much detail about constraints, this means Show m implies that m :: *. However, the definition of Thread passes an argument to m in the definition of its Atomic constructor, which has a field of type m (Thread m r). Look at the kind of Thread:

> :kind Thread
Thread :: (* -> *) -> * -> *

That implies that m :: * -> *, hence the mismatch.

The next error is in the implementation of your Show instance, namely:

show (Atomic m x) = "Atomic " ++ show m ++ " " ++ show x
               -                        ----------------

Here you’ve provided a pattern that matches multiple fields, but Atomic only has one field. You should change the implementation to the following:

show (Atomic m) = "Atomic " ++ show m

If you remove the Show m constraint, you’ll see a more useful error message:

Could not deduce (Show (m (Thread m r)))
  arising from a use of ‘show’
from the context (Show r)
  bound by the instance declaration at …
In the second argument of ‘(++)’, namely ‘show m’
In the expression: "Atomic " ++ show m
In an equation for ‘show’: show (Atomic m) = "Atomic " ++ show m

This says that you’re trying to call show on a value of type m (Thread m r) but you don’t have that constraint in the context. So you can add it:

instance (Show (m (Thread m r)), Show r) => Show (Thread m r) where
          ---------------------

This is not “standard” Haskell, so GHC starts suggesting extensions that allow it:

Non type-variable argument in the constraint: Show (m a)
(Use FlexibleContexts to permit this)
In the context: (Show (m a), Show r)
While checking an instance declaration
In the instance declaration for ‘Show (Thread m r)’

Let’s try adding -XFlexibleContexts (on the command line with ghci … -XFlexibleContexts, in a session with :set -XFlexibleContexts, or in a source file with {-# LANGUAGE FlexibleContexts #-}), since it’s actually a pretty benign extension. Now we get a different error:

Variable ‘a’ occurs more often than in the instance head
  in the constraint: Show (m a)
(Use UndecidableInstances to permit this)
In the instance declaration for ‘Show (Thread m r)’

We can add -XUndecidableInstances—all this means is that you’re writing a type-level computation that GHC can’t prove will halt. Sometimes this is undesirable, but in this case it’s fine, because we know that instance resolution will either find an acceptable Show instance or fail. Now the compiler accepts it, and we can try our Show instance, say with something simple like m ~ [] and r ~ Int:

> Atomic [Atomic [Return 1, Return 2]] :: Thread [] Int
Atomic [Atomic [Return 1,Return 2]]

However, note that this won’t work when you set m to a type constructor that doesn’t have any Show instances, such as IO:

> Atomic (return (Atomic (return (Return 1) >> return (Return 2)))) :: Thread IO Int

No instance for (Show (IO (Thread IO Int)))
  arising from a use of ‘print’
In a stmt of an interactive GHCi command: print it

Additionally, you may also notice that you’re missing some parentheses in the result of your Show instance:

> Atomic (Right (Atomic (Left "asdf"))) :: Thread (Either String) Int
Atomic Right Atomic Left "asdf"

That’s an easy fix that I’ll leave to you.

This should enable your instance to work with a datatype such as Toy from the article, by way of Free:

> Atomic (Free (Output "foo" (Pure (Return "bar"))))
Atomic (Free (Output "foo" (Pure Return ("bar"))))