recursivos - Simplificación simbólica en Haskell(¿usando recursividad?)

mayor de tres numeros en haskell

Question

¿Cómo puedo dar una regla general que incluya todas las expresiones a continuación? Por ejemplo, una expresión, otra para sub y otra para mult. Necesito usar la recursión, pero me confundí ...

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

Answer 1

La recursión aparece cuando necesita tratar con expresiones anidadas. Por ejemplo, ¿cómo lo hace simplemente (Plus (Plus 2 3) (Plus 4 5))?

Un enfoque es dividirlo en dos funciones. Mueva la lógica de un nivel (que muestra arriba) a su propia función. La función de simplificación principal puede tener una regla similar a la siguiente para Plus:

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

Answer 2

Primero: sé bastante poco acerca de Haskell, y mi tiempo total dedicado a programar el idioma no es más de 8 horas repartidas en 5 años más o menos, aunque he leído mucho sobre el idioma. Por lo tanto, perdona mi estilo sin duda horrible.

Abordé este problema ya que parecía una manera fácil de entrar en un poco de programación de Haskell. Primero, hice un tipo de datos inspirado en la muestra:

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

Lo hice un poco más simple que el original, y dejé fuera a Minus, pero de lo contrario es lo mismo.

Descubrí rápidamente que los valores construidos usando, por ejemplo, "Const 4" no eran imprimibles con los anteriores, ya que no había ninguna función de show aplicable. Hice Expr una instancia de la clase Show type, y proporcioné una definición simple de show, teniendo en cuenta la precedencia del operador:

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) ++ ")"

El siguiente paso fue la tarea de simplificación en sí. Como apunta Glomek, hay un problema al tratar de evaluar todo simplemente usando la coincidencia de patrones en una función.

Específicamente, para cualquier operación dada (todas las operaciones en el ejemplo son binarias) primero le gustaría simplificar el árbol izquierdo, luego el árbol derecho, y luego simplificar el Expr actual en base a lo que esos subárboles evaluaron; por ejemplo, si ambos se simplifican a Const, entonces puede reemplazar todo el subárbol con la operación evaluada. Sin embargo, la coincidencia de patrones te obliga a elegir qué hacer en función de los hijos del nodo inmediato, en lugar de lo que devuelven los subárboles después de simplificarse ellos mismos.

Por lo tanto, para que la coincidencia de patrones haga el trabajo de decidir si se evalúa el nodo actual o no como una subexpresión constante, es importante simplificar los subárboles, luego despacharlos en base al conjunto simplificado.

Hice esto usando una función separada que llamé eval, cuyo propósito es hacer coincidir patrones en cosas que se pueden reducir, suponiendo que los subárboles ya se hayan reducido. También maneja la multiplicación por 0 y 1, y la adición de 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

Ahora que tengo eval, y sé que es seguro llamar al nivel superior de un árbol de expresiones (es decir, no repetirá infinitamente), puedo llamarlo desde simplify luego de simplificar los subárboles:

-- 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

Esta versión de simplify tiene muchas limitaciones: no distribuirá una multiplicación sobre un subárbol no Const, no reordenará la expresión para juntar expresiones constantes (por lo que el equivalente a 1 + a + 2 no se simplificará a a + 3), etc. Sin embargo, realiza los trabajos básicos.