逻辑表达式评估器Haskell

Question

我写了以下逻辑表达式求值器.它适用于简单的2成员表达式,并且它会运行,但会为包含其他表达式的表达式产生错误,作为第二个/第一个成员.这是我的代码.

data Expression = Literal Bool | Operation Operator Expression Expression
data Operator = AND | OR

eval :: Expression -> Bool
eval (Literal x)                    = x
eval (Operation AND (Literal x) (Literal y))
 | x == True && y == True           = True
 | otherwise                        = False
eval (Operation OR (Literal x) (Literal y))
 | x == False && y == False         = False
 | otherwise                        = True

使用此输入调用时,它可以正常工作:

main = do
print $ eval (Operation OR (Literal False) (Literal False))

但使用此输入调用时会产生错误:

main = do
print $ eval( Operation OR (Literal True) (Operation AND (Literal True) (Literal False)) )

Answer 1

你eval的水平太低了.通过Literal在签名中包含s.更好的方法是使用递归:

eval :: Expression -> Bool
eval (Literal x) = x
eval (Operation AND x y) = (eval x) && (eval y)
eval (Operation OR x y) = (eval x) || (eval y)

换句话说呼吁eval在右手边.如果它是a Literal,它将立即解析为正确的值,如果它是级联表达式,它也将解决它Operation _ _ _.

一般情况下,不建议启动级联模式匹配(好的,有时它很有用).在这种情况下,你至少应该问自己是否没有更优雅的解决方案.

这段代码很容易显示函数是完全的(无论输入如何,它总是会产生一个结果).你的代码不是这种情况.始终尝试执行整体检查.

编辑

如果Operations 的数量将显着增加,您最好将关注点分离为handler :: Operation -> Bool -> Bool -> Bool函数和eval函数.就像是:

data Expression = Literal Bool | Operation Operator Expression Expression
data Operator = AND | OR | XOR

handler :: Operation -> Bool -> Bool -> Bool
handler AND = (&&)
handler OR = (||)
handler XOR = xor
    where xor True False = True
          xor False True = True
          xor _ _ = False

eval :: Expression -> Bool
eval (Literal x) = x
eval (Operation o x y) = (handler o) (eval x) (eval y)

如果你需要处理a NOT,那是另一种表达式:

data Expression = Literal Bool | Operation Operator Expression Expression | OperationU OperatorU Expression

OperatorU在这里是一个一元的运营商.例如:

data OperatorU = ID | NOT

与ID身份.现在在这种情况下,您可以定义第二个处理程序:

handlerU :: OperatorU -> Bool -> Bool
handlerU ID = id
handlerU NOT = not

然后eval读:

eval :: Expression -> Bool
eval (Literal x) = x
eval (Operation o x y) = (handler o) (eval x) (eval y)
eval (OperationU o x) = (handlerU o) (eval x)