0

I'm trying to write a function that evaluates a nested boolean data type. My issue comes from comparing a data type within a data type. The first two (Lit and Or) compile fine but I don't understand how to incorporate the first type into the function of the SecondExpr. As I type it out, I feel like I'm taking the longest way possible when something shorter works.

Here are the two data types.

data Expr = Val Int
          | Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          | If SecondExpr Expr Expr

data SecondExpr = Lit Bool
                | Or SecondExpr SecondExpr 
                | EqualTo Expr Expr
                | LessThan Expr Expr

(Another issue I'm having is creating examples of SecondExpr to test because, conceptually, I see every Expr as the 6 different types of Expr. That means, for every Expr Expr there would be hundreds of guards.)

Below is the code so far:

eval :: SecondExpr -> Bool
eval (Lit n)                   = n
eval (Or e1 e2)
  | True && True               = True
  | True && False              = True
  | False && True              = True
  | otherwise                  = False
eval (EqualTo e1 e2)
  | (Add e1 e2) == (Add e1 e2) = True
  | (Sub e1 e2) == (Sub e1 e2) = True
  | (Mul e1 e2) == (Mul e1 e2) = True
  | (Div e1 e2) == (Div e1 e2) = True
  | otherwise                  = False
eval (LessThan e1 e2)
  | (Add e1 e2) == (Add e1 e2) = True
  | (Sub e1 e2) == (Sub e1 e2) = True
  | (Mul e1 e2) == (Mul e1 e2) = True
  | (Div e1 e2) == (Div e1 e2) = True
  | otherwise                  = False

This is the error I get:

    * No instance for (Eq Expr) arising from a use of `=='
    * In the expression: (Add e1 e2) == (Add e1 e2)
      In a stmt of a pattern guard for
                     an equation for `eval':
        (Add e1 e2) == (Add e1 e2)
      In an equation for `eval':
          eval (EqualTo e1 e2)
            | (Add e1 e2) == (Add e1 e2) = True
            | (Sub e1 e2) == (Sub e1 e2) = True
            | (Mul e1 e2) == (Mul e1 e2) = True
            | (Div e1 e2) == (Div e1 e2) = True
            | otherwise = False
   |
24 |   | (Add e1 e2)       == (Add e1 e2) = True
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

So I know my syntax is wrong but how do you substitute an Expression within the function of an Expression?

Improve this question
2
  • 1
    True && True is the same as just True. A guard expression of | True always succeeds; it's like having no guard at all: eval (Or e1 e2) = True. Commented Apr 23, 2019 at 23:01
  • 1
    I'm unclear what SecondExpr is for. You probably want eg. eval (Or e1 e2) = eval e1 || eval e2 rather than what you've written, which is constant True. For EqualTo, you'll need an eval' on Expr to some equatable type, then just eval (EqualTo e1 e2) = eval' e1 == eval' e2 (and you can see how to easily adapt that for LessThan). This also solves the issue of combinatorial explosion you observed, though as I said the overall design seems questionable but hard to be more helpful without more context. Commented Apr 23, 2019 at 23:04

1 Answer 1

Reset to default
4

You're going to need two evaluation functions:

evalNum :: Expr -> Int

and

evalBool :: SecondExpr -> Bool

Neither of them should use any guards (| ...).

For example, evalBool would look like this:

evalBool (Lit n) = n
evalBool (Or e1 e2) = evalBool e1 || evalBool e2
evalBool (EqualTo e1 e2) = evalNum e1 == evalNum e2
evalBool (LessThan e1 e2) = evalNum e1 < evalNum e2

Subexpressions are evaluated recursively with their corresponding eval functions, and the results are combined using appropriate Haskell operators (such as ||, ==, <).

Implementing evalNum is left as an exercise for the reader.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.