Haskell中的符号简化(使用递归？)

Question

我如何给出包含以下所有表达式的一般规则？例如一个表达式,另一个用于sub,一个用于mult.我需要使用递归,但我感到困惑......

simplify :: Expr->Expr

simplify (Mult (Const 0)(Var"x"))
 = Const 0 
simplify (Mult (Var "x") (Const 0))
 = Const 0
simplify (Plus (Const 0) (Var "x")) 
= Var "x"
simplify (Plus (Var "x") (Const 0))
 = Var "x" 
simplify (Mult (Const 1) (Var"x")) 
= Var "x"
simplify (Mult(Var"x") (Const 1))
 = Var "x" 
simplify (Minus (Var"x") (Const 0))
 = Var "x"
simplify (Plus (Const x) (Const y)) 
= Const (x + y)
simplify (Minus (Const x) (Const y))
= Const (x - y)
simplify (Mult (Const x) (Const y))
 = Const (x * y)
simplify x = x

Answer 1

首先:我对Haskell知之甚少,而且花在编程语言上的总时间在5年左右的时间内传播时间不超过8小时,尽管我已经阅读了很多关于语言的内容.因此,原谅我无疑的可怕风格.

我解决了这个问题,因为它看起来像是一种简单的方法来进入一些Haskell编程.首先,我根据示例创建了一个数据类型:

data Expr = Const Int | Mult Expr Expr | Plus Expr Expr | Var String

我把它做得比原版简单一点,并且留下了Minus,但是否则它是一样的.

我很快发现使用例如"Const 4"构造的值不能用上面的方法打印,因为没有适用的show函数.我使Expr成为Show类的一个实例,并提供了一个简单的show定义,将运算符优先级考虑在内:

instance Show Expr where
    show (Const n) = show n
    show (Var n) = show n
    show (Plus a b) = (show a) ++ "+" ++ (show b)
    show (Mult a b) = "(" ++ (show a) ++ ") * (" ++ (show b) ++ ")"

接下来是简化任务本身.正如Glomek提示的那样,尝试在一个函数中使用模式匹配来评估所有内容时存在问题.

具体来说,对于任何给定的操作(示例中的所有操作都是二进制),您首先要简化左树,然后是右树,然后根据这些子树评估的内容简化当前的Expr; 例如,如果两者都简化为Const,那么您可以用评估的操作替换整个子树.但是,模式匹配会强制您根据直接节点的子节点选择要执行的操作,而不是在自我简化后返回子树后返回的内容.

因此,要使模式匹配完成决定是否将当前节点作为常量子表达式进行评估的工作,重要的是简化子树,然后根据简化的整体进行调度.

我使用一个名为eval的单独函数来完成此操作,其目的是对可以减少的事物进行模式匹配,假设已经减少了子树.它还处理乘以0和1,并加0:

-- Tries to evaluate any constant expressions.
eval :: Expr -> Expr
eval (Mult (Const a) (Const b)) = Const (a * b)
eval (Mult (Const a) b)
    | a == 0 = Const 0
    | a == 1 = b
    | otherwise = (Mult (Const a) b)
eval (Mult a (Const b))
    | b == 0 = Const 0
    | b == 1 = a
    | otherwise = (Mult a (Const b))
eval (Plus (Const a) (Const b)) = Const (a + b)
eval (Plus (Const a) b)
    | a == 0 = b
    | otherwise = (Plus (Const a) b)
eval (Plus a (Const b))
    | b == 0 = a
    | otherwise = (Plus a (Const b))
eval e = e

既然我有eval,并且我知道在表达式树的顶层调用是安全的(即它不会无限递归),我可以在简化子树后从简化中调用它:

-- Tries to match evaluation rules after simplifying subtrees.
simplify :: Expr -> Expr
simplify (Plus a b) = eval (Plus (simplify a) (simplify b))
simplify (Mult a b) = eval (Mult (simplify a) (simplify b))
simplify e = e

这个版本的简化有很多限制:它不会在非Const子树上分配乘法,它不会重新排序表达式以将常量表达式组合在一起(因此等效于1 + a + 2将不会简化为a + 3)等等.然而,它完成了基本的工作.