making types: Add data type and evaluator that is of an unmatched type

Question

I have added | Lit Int and | Add Exp Exp to the data type as seen below, along with the evaluation. However I get an error "Couldn't match expected type ‘Var’ with actual type ‘Int’".

data Exp = V Var
    | B Bool
    | L Exp
    | A Exp Exp
    | Lit Int
    | Add Exp Exp
data Var = VZ |VS Var

eval:: Exp -> Var
eval (Lit n)     = n
eval (Add e1 e2) = eval e1 + eval e2

How can I add Int and Add to the data type, along with the evaluation, but maintain the following code as is. Is this possible?

data Exp = V Var
    | B Bool
    | L Exp
    | A Exp Exp
data Var = VZ |VS Var

I have added an instance to resolve this, as seen below, but now I have the error "Pattern bindings (except simple variables) not allowed in instance declaration: Add e1 e2 = (Lit e1) + (Lit e2)":

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}

data Exp = V Var
    | B Bool
    | L Exp
    | A Exp Exp
    | Lit Int
    | Add Exp Exp
data Var = VZ |VS Var

eval:: Exp -> Var
eval (Lit n)     = n
eval (Add e1 e2) = eval e1 + eval e2

instance Num Var where
    Lit e = e

instance Num Var where
    Add e1 e2 = (Lit e1) + (Lit e2)

eval has type Exp -> Var, so that means that eval e1 is a Var. But you can not add two Vars together, or at least not without defining how to do that. — Willem Van Onsem
you define it as an instance of Num, so instance Num Var where .... — Willem Van Onsem
VZ and VS are part of code that I am working with, I don't actually see them defined further so I can probably drop it — pmichaels

dfeuer dfeuer · Accepted Answer · 2020-10-25T17:52:27

You seem to have gotten mixed up along the way. I believe Var represents a free variable in De Bruijn notation. You're missing an encoding of values. This could look something vaguely like

data Value
  = IntVal !Int
  | BoolVal !Bool
  | Closure { environment :: [Value]
            , expr :: Exp }

Now you'll want eval :: Exp -> Value to evaluate expressions. There's lots of work left.

making types: Add data type and evaluator that is of an unmatched type

1 Answers