Haskell中的符号简化（使用递归？） [英] Symbolic simplification in Haskell (using recursion?)
问题描述
我如何给出一个包含以下所有表达式的一般规则？
例如一个表达式，另一个表示子表达式，另一个表示多表达式。
我需要使用递归，但是我感到困惑......
$ $ $ $ $ $ $ $ $ $> simplified :: Expr-> Expr
$ b $ simpl（Mult（Const 0）（Varx））
= Const 0
simpl（Mult（Varx）（Const 0））
= Const 0
simpl（Plus（Const 0）（Varx））
= Varx
simpl（Plus（Varx）（Const 0））
= Varx
simpl（Mult（Const 1）（Varx））
= Varx
simpl（Mult（Varx）（Const 1） ）
= Varx
simpl（Minus（Varx）（Const 0））
= Varx
simpl（Plus（Const x）（Const y）
= Const（x + y）
simplify（Minus（Const x）（Const y））
= Const（x - y） x）
= Const（x * y）
简化x = x
我解决了这个问题，因为它看起来像一个简单的方法来进入一点Haskell编程。首先，我制作了一个受样本启发的数据类型：
data Expr = Const Int | Mult Expr Expr |加上Expr Expr | Var字符串
我使它比原来简单一些，并省略了Minus，但除此之外它是同样的。
我很快发现使用eg由于没有适用的演出功能，因此Const 4不能打印上述内容。我将Expr作为Show类的一个实例，并提供了show的一个简单定义，并将运算符优先级考虑在内：
instance Show Expr where
show（Const n）= show n
show（Var n）= show n
show（Plus ab）=（show a）+++++（show b）
show（Mult ab）=（++（show a）++）*（++（show b）++）
接下来是简化任务本身。正如Glomek所暗示的那样，在一个函数中尝试使用模式匹配来评估所有内容是个问题。
具体来说，对于任何给定的操作（示例中的所有操作都是二进制）你想首先简化左树，然后右树，然后根据这些子树的评估结果简化当前的Expr;例如如果两者都简化为Const，那么可以用评估操作替换整个子树。然而，模式匹配迫使您根据直接节点的子节点来选择要执行的操作，而不是根据子树在简化后返回的结果。
因此，匹配做决定是否评估当前节点的工作或不是一个常量子表达式，重要的是简化子树，然后基于简化的整体进行调度。
我使用一个名为eval的单独函数做了这个工作，假设子树已经被减少，其目的是模式匹配可以减少的东西。它还处理乘法0和1，并加上0：
- 尝试评估任何常量表达式。
eval :: Expr - > Expr
eval（Mult（Const a）（Const b））= Const（a * b）
eval（Mult（Const a）b）
| a == 0 = Const 0
| a == 1 = b
|否则=（Mult（Const a）b）
eval（Mult a（Const b））
| b == 0 = Const 0
| b == 1 = a
|否则=（Mult a（Const b））
eval（Plus（Const a）（Const b））= Const（a + b）
eval（Plus（Const a）b）
| a == 0 = b
|否则=（Plus（Const a）b）
eval（Plus a（Const b））
| b == 0 = a
|否则=（加一个（Const b））
eval e = e
现在我有eval，我知道在表达式树的顶层调用是安全的（即它不会无限递归），我可以在简化子树后简化它：
- 尝试在简化子树后匹配评估规则。
简化:: Expr - >
简化（加ab）= eval（加（简化a）（简化b））
简化（Mult ab）= eval（简化a）（简化b））
简化e = e
这个简化版本有很多限制：它不会将乘法分配给非-Const子树，它不会重新排列表达式以将常量表达式组合在一起（所以1 + a + 2的等价物不会简化为+ 3）等等。但是，它完成了基本工作。 p>
How can I give a general rule that includes all the expressions below? E.g one expression, another one for sub and one for mult. I need to use recursion but i got confused...
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
First up: I know reasonably little about Haskell, and my total time spent programming the language is no more than 8 hours spread over 5 years or so, though I have read plenty about the language. Thus, forgive my no doubt horrible style.
I tackled this problem since it looked like an easy way to get into a little bit of Haskell programming. First up, I made a data type inspired by the sample:
data Expr = Const Int | Mult Expr Expr | Plus Expr Expr | Var String
I made it a little simpler than the original, and left out Minus, but otherwise it's the same.
I quickly found out that values constructed using e.g. "Const 4" were not printable with the above, as there was no show function applicable. I made Expr an instance of the Show type class, and provided a simple definition of show, taking operator precedence into account:
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) ++ ")"
Next up was the simplification task itself. As Glomek hints, there's an issue with trying to evaluate everything just using pattern matching in one function.
Specifically, for any given operation (all operations in the example are binary) you'd like to first simplify the left tree, then the right tree, and then simplify the current Expr based on what those subtrees evaluated to; e.g. if both simplified to Const, then you can replace the entire subtree with the evaluated operation. However, pattern matching forces you to choose what to do based on the immediate node's children, rather than what the subtrees return after being simplified themselves.
Thus, to get pattern-matching to do the job of deciding whether to evaluate the current node or not as a constant subexpression, it's important to simplify the subtrees, then dispatch based on the simplified whole.
I did this using a separate function I called eval, whose purpose is to pattern-match on things that can be reduced, assuming that subtrees have already been reduced. It also handles multiplication by 0 and 1, and addition of 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
Now that I have eval, and I know it's safe to call at the top level of an expression tree (i.e. it won't infinitely recurse), I can call it from simplify after I've simplified the subtrees:
-- 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
This version of simplify has many limitations: it won't distribute a multiplication over a non-Const subtree, it won't reorder the expression to bring constant expressions together (so the equivalent of 1+a+2 won't get simplified to a+3), etc. However, it gets the basic jobs done.
这篇关于Haskell中的符号简化（使用递归？）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
