Haskell adding a polymorphic type

Question

I am trying to add a polymorphic == to a data type. I have added the POLYEQ Var Var to data Exp and added Eval1 and Eval2:

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}

data Exp = V Var
    | B Bool
    | L Exp
    | A Exp Exp
    | MyInt Int
    | And Exp Exp
    | Or Exp Exp
    | Not Exp
    | Mult Exp Exp
    | UnaryNeg Exp
    | LEQ Exp Exp
    | LESST Exp Exp
    | Add Exp Exp 
    | POLYEQ Var Var
data Var = VZ |VS Var

eval:: Exp -> Int
eval (MyInt e4)     = e4
eval (UnaryNeg e10)     = - (eval e10)
eval (Mult e11 e12) = eval e11 * eval e12
eval (Add e1 e2) = eval e1 + eval e2

eval0:: Exp -> Bool
eval0 (B e5) = e5
eval0 (Not e3) = not (eval0 e3)
eval0 (And e6 e7) = (eval0 e6) && (eval0 e7)
eval0 (Or e8 e9) = (eval0 e8) || (eval0 e9)
eval0 (LEQ e13 e14) = eval e13 <= eval e14
eval0 (LESST e15 e16) = eval e15 < eval e16

eval2:: Exp -> Var
eval2 (V e22) = e22

eval1:: a -> Bool
eval1 (POLYEQ e19 e20) = eval2 e19 == eval2 e20

But I get the followng error;

Exp.hs:37:32: error:

• Couldn't match expected type ‘Exp’ with actual type ‘Var’

• In the first argument of ‘eval2’, namely ‘e19’

  In the first argument of ‘(==)’, namely ‘eval2 e19’

  In the expression: eval2 e19 == eval2 e20

Exp.hs:37:45: error:

• Couldn't match expected type ‘Exp’ with actual type ‘Var’

• In the first argument of ‘eval2’, namely ‘e20’

  In the second argument of ‘(==)’, namely ‘eval2 e20’

  In the expression: eval2 e19 == eval2 e20

Failed, modules loaded: none.

How can I make the == polymorphic?

edit:

eval1:: Exp -> Bool
eval1 (POLYEQ e19 e20) = eval e19 == eval e20

The file loads now, but when I run ti1 = POLYEQ (MyInt 4) (MyInt 7) followed by eval1 ti1 I get the following error:

:100:7: error: • Couldn't match expected type ‘Exp’

              with actual type ‘Exp -> Exp -> Exp’

• Probable cause: ‘POLYEQ’ is applied to too few arguments

  In the first argument of ‘eval1’, namely ‘POLYEQ’

  In the expression: eval1 POLYEQ

  In an equation for ‘it’: it = eval1 POLYEQ

Many things look suspicious. Why does the equality take two variables instead of two expressions? You also have defined a bunch of partial functions. You might be needing a type for values like data Value = VI Int | VB Bool to represent the value of an expression of unknown type. — chi
Okay, how do I change the eval1 and eval2 to be polymorphic? — pmichaels

Jon Purdy Jon Purdy · Accepted Answer · 2020-10-25T20:25:15

There are several issues with your code. First, to solve your actual problem, you should make the fields of the POLYEQ constructor of type Exp, not Var, otherwise you will only be able to compare variables.

Second, you should not split the eval function into multiple definitions like this. It looks like you’ve done so in order to return different types of results from each one: Int or Bool. But the effect of writing your code this way is that all of these functions are partial: eval0 will only work on a subset of expressions, and will crash on others, and you can’t know ahead of time which function to call on an arbitrary Exp without examining it first.

A simple conventional approach is to add a type of values resulting from evaluation, for example:

data Val
  = IntVal Int
  | BoolVal Bool

With this, you can consolidate your functions into one, and tag the result of each case with the appropriate Val constructor. In addition, you don’t need to name all of your variables with distinct names, since they’re local to each case.

eval :: Exp -> Val

-- Evaluation of literals: tag the value with its type.
eval (MyInt i) = IntVal i
eval (B b) = BoolVal b

-- Evaluation of integer operations: match on ‘IntVal’.
-- This will raise an error if the expression did not return an integer.
eval (UnaryNeg e) = let
  IntVal i = eval e  -- Unwrap result, asserting that it’s an integer.
  in IntVal (- i)    -- Rewrap in ‘IntVal’ after applying negation.

eval (Mult e1 e2) = let
  IntVal i1 = eval e1
  IntVal i2 = eval e2
  in IntVal (i1 * i2)

-- Instead of just crashing, you may use explicit
-- pattern matching and handle the type error:
eval (Add e1 e2) = case (eval e1, eval e2) of
  (IntVal i1, IntVal i2) -> IntVal (i1 + i2)
  _ -> ... -- Decide what to do in the error case.

-- Fill in the remaining cases for each ‘Exp’ constructor.

For the POLYEQ case, you need to match on the results of evaluation to assert that they’re the same type, and compare accordingly:

eval (POLYEQ e1 e2) = case (eval e1, eval e2) of
  (IntVal i1, IntVal i2) -> BoolVal (i1 == i2)
  (BoolVal b1, BoolVal b2) -> BoolVal (b1 == b2)
  _ -> ... -- What do you want to do in this case?
           -- Return ‘BoolVal False’, raise an error, or something else?

However, this doesn’t describe how to evaluate lambda expressions (L) and variables. For that, you’ll need to add an additional argument to eval containing the variable environment (for example, a [Val], where VZ looks up from the head, and VS looks up within the tail), and another constructor for Val to store a function value with its environment. However, this is beyond the scope of your current question.

Haskell adding a polymorphic type

1 Answers