Expected a type, but has kind ‘* -> Constraint’

user_858962 0
Viewed 5420

I'm writing a calculator to add and subtract numbers. I have two abstractions here, an Expr, which is modeled as a tree, and a typeclass Operand, which comprise the left and right nodes of the tree. Operands have a function combine that apply a function to the left and right nodes:

module Data.Calculator where

class Operand a where
    combine :: a -> a

data Operator = Plus | Minus
data Expr = Node Operator Operand Operand | Value Integer

instance Operand Expr where
    combine (Node op left right) =
        case op of 
            Plus -> (combine left) + (combine right)
            Minus -> (combine left) - (combine right)
    combine (Value a) = (Value a)

instance Num Expr where
    (+) (Value left) (Value right) = Value (left + right)
    (*) (Value left) (Value right) = Value (left * right)
    abs (Value a) = Value (abs a)
    fromInteger i = Value i
    negate (Value a) = Value (negate a)

When I try to compile this, I get the error

calculator/src/Data/Calculator.hs:7:35: error:

    • Expecting one more argument to ‘Operand’
      Expected a type, but ‘Operand’ has kind ‘* -> Constraint’
    • In the type ‘Operand’
      In the definition of data constructor ‘Node’
      In the data declaration for ‘Expr’
  |
  | data Expr = Node Operator Operand Operand | Value Integer

What does this mean? I'm aware that this problem can be solved without defining Operand as a typeclass, but I'd like to use the Operand typeclass, since that is a subject I'm learning about now. What am I doing wrong?

haskell
1 Answers

In your code Operand is not a type, but class of types. There can be no values of type Operand, because it's not a data type. Therefore, you can't use it as part of the definition of Expr.

The cryptic notation * -> Constraint means that the identifier Operand, if applied to a type (denoted *), will give you a Constraint. The compiler says that it expected a type in that context (such as Int or String or Maybe Float, etc.), but you gave it Operand, which has kind * -> Constraint.

From your code, I'm guessing what you actually meant to do was to construct Expr in such a way that it can contain values of any types, as long as those types have an instance of Operand. Would that be a correct assumption?

If so, then the way to do that is to wrap those values in an existential type:

data SomeOperand = forall a. Operand a => SomeOperand a

Or same thing in GADT notation:

data SomeOperand where
    SomeOperand :: forall a. Operand a => a -> SomeOperand

These notations literally say that type SomeOperand wraps exactly one value a, which must have an instance of Operand.

Now you can use SomeOperand in the definition of Expr:

data Expr = Node Operator SomeOperand SomeOperand | Value Integer

Now, when matching on Expr, you'll get a value that has an instance of Operand, and so you'll be able to apply combine to it:

f :: Expr -> Expr
f (Node op (SomeOperand a) (SomeOperand b)) = Expr op (combine a) (combine b)
f (Value i) = Value i

Notice that you can't really do anything with such operands except convert them to other values of the same type, which again leaves you nowhere. In order for this to be useful in any way, the class Operand must have some methods for converting to something other than the type itself, for example:

class Operand a where
    combine :: a -> a
    showOperand :: a -> String

Now I can use showOperand to a useful end:

showExpr :: Expr -> Expr
showExpr (Node op (SomeOperand a) (SomeOperand b)) = showOperand a ++ show op ++ showOperand b
showExpr (Value i) = show i
user_1802860
Related