¿Cómo puedo simplificar una expresión aritmética básica?

Question

¿Cómo puedo simplificar una expresión aritmética básica?

p. Ej.

module ExprOps where 

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

¿Qué tengo que hacer?

---

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) 

Las simplificaciones que tengo en mente son:

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

y simplificando subexpresiones constantes, por ejemplo Plus (Const 1) (Const 2) se convertiría en Const 3. No esperaría que las variables (o variables y constantes) se concatenan: Var "st" es una variable distinta de Var "s".

Lo que quiero lograr es crear un módulo similar a la anterior que utiliza una función llamada simplify :: Expr->Expr racionales

Answer 1

estamos hablando aquí, como racionales de GMP? Si es así, entonces uno podría simplificar una división haciendo que el segundo argumento sea recíproco y luego se multiplique.

Aparte de eso, la multiplicación se realiza más de una vez, y la división se resta más de una vez.

Como dijo Mitch en los comentarios, podríamos hacernos con más información acerca de lo que intentas simplificar.

Answer 2

Bueno, usted tiene el modelo general correcto. Solo necesita más reglas y aplicar recursivamente el proceso de simplificación.

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 

Answer 3

Hice algo así como un proyecto para una clase de IA hace décadas. La clase usó LISP, así que lo primero que hice fue convertir la expresión de la notación infija a una S-Expression.

Luego se trataba de atravesar el "árbol" recursivamente y aplicar un conjunto de reglas en cada nodo. p.ej. si este nodo contiene una operación cuyos operandos son ambas constantes, realice la operación ahora y reemplace el nodo con el resultado.

Una vez que la funcionalidad básica estaba en su lugar, era una cuestión de agregar nuevas reglas de simplificación al sistema.

Finalmente, la S-Expression se convirtió de nuevo a notación infija para su visualización.

Answer 4

Solo para darle un ejemplo, aquí hay una función que simplificaría la expresión que dio. La idea es que cada definición de simplificar se intente de arriba abajo hasta que coincida uno de los patrones en el lado izquierdo del signo igual. El propósito de la última definición es salir de la recursión si no hay una forma conocida de simplificar más.

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