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

Question

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

6

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

例如：

module ExprOps where 

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

我需要做什么？

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)

我所想的简化包括：

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

简化常量子表达式，例如 Plus (Const 1) (Const 2) 将变为 Const 3。我不希望将变量（或变量和常量）连接起来：Var "st" 是一个不同的变量，与 Var "s" 不同。

我的目标是创建一个类似上面的模块，使用名为 simplify :: Expr->Expr 的函数。

- user41000

4个回答

1

举个例子，这里有一个函数可以简化你给出的表达式。其思想是从上到下尝试每个simplify的定义，直到等号左边的某个模式匹配成功。最后一个定义的目的是在没有已知的进一步简化方法时跳出递归。

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

- Michael Steele

1

几十年前，我在一门人工智能课程中做了一个类似的项目。当时我们使用的是LISP语言，所以我首先将表达式从中缀表示法转换为S-Expression。

然后，就是递归地遍历“树”，并在每个节点应用一组规则。例如，如果该节点包含一个操作符，其操作数都是常量，则立即执行该操作并用结果替换该节点。

一旦基本功能就位，就可以向系统添加新的简化规则。

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

- Ferruccio

0

我们在谈论有理数吗，比如GMP的有理数？如果是这样，那么可以通过将第二个参数变为其倒数然后相乘来简化除法。

除此之外，乘法是多次执行加法，而除法是多次执行减法。

正如Mitch在评论中所说，我们需要更多关于您要简化的内容的信息。

- boost

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Edward Kmett · Accepted Answer

嗯，你有正确的总体模型。你只需要更多规则并递归应用简化过程。

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