haskell - Haskell 中的算术表达式求值

Question

在这里，我尝试使用 Exp 数据类型的定义值来评估 Haskell 中的表达式。函数类型为 eval::Exp -> Int 数据类型为:

data Exp = Num Int
       | Exp :+: Exp
       | Exp :-: Exp
       | Exp :*: Exp
       | Exp :/: Exp
       deriving (Show)

我试图评估的值(value)观是:

 4 + 5 * 6 , respecting correct precedences of the operators
 4 + 5 + 6 , respecting, that + binds left-associative
 (4 + 3) * (5 - 2)
 4 + (4 / (2 - 2))

到目前为止，这个逻辑运行良好，即:

eval :: Exp -> Int
eval (Num a) = a 
eval (a :+: b) = (eval a) + (eval b)
eval (a :-: b) = (eval a) - (eval b)
eval (a :*: b) = (eval a) * (eval b)
eval (a :/: b) = (eval a) `div` (eval b)

当我通过这个时，我得到 3 作为正确的输出:

eval (Num 2 :+: Num 2 :-: Num 1) 
output = 3 

但我很困惑它是如何计算表达式的第二部分的 :-: 据我所知，在第一次迭代中匹配的唯一模式是 eval (a :+: b) = (eval a) + (eval b) 返回 4 作为输出 它如何携带 4 到下一次迭代以执行 :-:操作？

在那之前我正在尝试这样的事情:

eval :: Exp -> Int
eval (Num a) = a
eval (<b>Num</b> a :+: <b>Num</b> b) = eval (<b>Num</b> a) + eval (<b>Num</b> b)
eval (<b>Num</b> a :-: <b>Num</b> b) = eval (<b>Num</b> a) - eval (<b>Num</b> b)
eval (<b>Num</b> a :*: <b>Num</b> b) = eval (<b>Num</b> a) * eval (<b>Num</b> b)
eval (<b>Num</b> a :/: <b>Num</b> b) = eval (<b>Num</b> a) `div` eval (<b>Num</b> b)

它没有给出想要的结果，然后我就把它改成了第一个版本。它工作正常但没有得到它的正确语义。有什么帮助吗？请不要犹豫，详细说明。提前致谢。

Answer 1

运算符的默认固定值是 infixl 9 (参见 4.4.2 固定性声明)。

您还没有为您的 :+: 等运算符声明固定性。

这意味着你的表达式被解析为

eval ((Num 2 :+: Num 2) :-: Num 1)  :: Exp

--     Num 2                        :: Exp 
--               Num 2              :: Exp 
--     Num 2 :+: Num 2              :: Exp 
--                          Num 1   :: Exp 
--    (Num 2 :+: Num 2) :-: Num 1   :: Exp 

所以评估进行为

  eval ((Num 2 :+: Num 2) :-: Num 1)  -- match with:
  eval (a                 :-: b    ) = (eval a) - (eval b)
                                     =  ....