Haskell中的符号简化（使用递归？）

如何给出包含以下所有表达式的一般规则？例如一个表达式，另一个表示子表达式，另一个表示mult。我需要使用递归，但我糊涂了......Haskell中的符号简化（使用递归？）

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

来源

2008-11-27 user41000

递归来当你需要处理嵌套表达的影响。例如，你怎么简单（Plus（Plus 2 3）（Plus 4 5））？

一种方法是将其分成两个功能。将上面显示的一级逻辑移动到它自己的函数中。主要简化功能可能有类似于加上以下规则：

simplify (Plus x y) = simplify_one_level (Plus (simplify x) (simplify y))

来源

2008-11-27 17:52:55 Glomek

首先是：我知道哈斯克尔相当小的，花了我的全部时间编程语言散布在5年内不超过8小时尽管我已经阅读了大量有关该语言的内容。因此，请原谅我毫无疑问的可怕风格。

我解决了这个问题，因为它看起来像一个简单的方法来进入一点Haskell编程。首先，我提出由样本的启发数据类型：

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

我把它比原来稍微简单，并留下了减，但除此之外，它是相同的。

我很快发现使用例如由于没有适用的演出功能，因此“Const 4”不能打印上述内容。我做了Expr的显示类型的类的实例，并提供了展示的一个简单的定义，考虑运算符的优先考虑：

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）等等。但是，它完成了基本的工作。

来源

2008-11-27 20:03:19

Haskell中的符号简化（使用递归？）

回答

相关问题