如何简化基本算术表达式？

How can I simplify a basic arithmetic expression?

如何简化基本算术表达式?

e.g.

module ExprOps where 

simplify :: Expr -> Expr
simplify (Plus(Var"x") (Const 0)) = Var "x"

What do I have to do?

我需要做什么?

module Expr where

-- Variables are named by strings, assumed to be identifiers.
type Variable = String

-- Representation of expressions.
data Expr = Const Integer
          | Var Variable
          | Plus Expr Expr
          | Minus Expr Expr
          | Mult Expr Expr
          deriving (Eq, Show)

The simplifications I have in mind are:

我想到的简化是:

0*e = e*0 = 0
1*e = e*1 = 0+e = e+0 = e-0 = e

and simplifying constant subexpressions, e.g. Plus (Const 1) (Const 2) would become Const 3. I would not expect variables (or variables and constants) to be concatenated: Var "st" is a distinct variable from Var "s".

并且简化了常数子表达式,例如:加(Const 1)(Const 2)将成为Const 3.我不希望连接变量(或变量和常量):Var“st”是Var“s”的不同变量。

What I want to achieve is to create a module like the one above that uses a function called simplify :: Expr->Expr

我想要实现的是创建一个类似上面的模块,它使用一个名为simplify :: Expr-> Expr的函数

4 个解决方案

#1

Well, you have the right general model. You just need more rules and to recursively apply the simplification process.

那么,你有正确的通用模型。您只需要更多规则并递归应用简化过程。

simplify :: Expr -> Expr 
simplify (Mult (Const 0) x) = Const 0 
simplify (Mult x (Const 0)) = Const 0
simplify (Plus (Const 0) x) = simplify x
simplify (Plus x (Const 0)) = simplify x 
simplify (Mult (Const 1) x) = simplify x 
simplify (Mult x (Const 1)) = simplify x 
simplify (Minus x (Const 0)) = simpify 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

#2

I did something like this as a project for an AI class decades ago. The class used LISP, so the first thing I did was to convert the expression from infix notation to an S-Expression.

几十年前,我做了类似这样的AI类项目。这个类使用了LISP,所以我做的第一件事就是将表达式从中缀表示法转换为S表达式。

Then it was a matter of traversing the "tree" recursively and applying a set of rules at each node. e.g. if this node contains an operation whose operands are both constants, perform the operation now and replace the node with the result.

然后,这是一个递归地遍历“树”并在每个节点处应用一组规则的问题。例如如果此节点包含操作数均为常量的操作,请立即执行操作并将结果替换为该节点。

Once the basic functionality was in place, it was a matter of adding new new simplification rules to the system.

一旦基本功能到位,就需要向系统添加新的简化规则。

Finally, the S-Expression was converted back to infix notation for display.

最后,S-Expression被转换回中缀表示法以供显示。

#3

Just to give you an example, here's a function that would simplify the expression you gave. The idea is that each definition of simplify is tried from top to bottom until one of the patterns on the left hand side of the equal sign matches. The purpose of the last definition is to break out of recursion if there is no known way to simplify any further.

只是举个例子,这是一个简化你给出的表达式的函数。我们的想法是,从上到下尝试每个简化定义,直到等号左侧的一个模式匹配为止。最后一个定义的目的是在没有任何已知方法进一步简化的情况下突破递归。

simplify :: Expr -> Expr
simplify (Plus l         (Const 0)) = simplify l
simplify (Plus (Const 0) r        ) = simplify r
simplify x                          = x

#4

Are we talking rationals here, like GMP's rationals? If so, then one could simplify a division by making the second argument into its reciprocal and then multiplying.

我们在这里谈论理性,就像GMP的理性一样吗?如果是这样,那么可以通过将第二个参数变为其倒数然后相乘来简化除法。

Apart from that, multiplication is addition done more than once, and division is subtraction done more than once.

除此之外,乘法是不止一次加法,而除法是多次减法。

As Mitch has said in the comments, we could do with some more information about what you're trying to simplify.

正如米奇在评论中所说,我们可以提供一些关于你想要简化的更多信息。

#1