simplificar: qué devuelve cada llamadaSeis reglas algebraicas escritas como casos de un
match, aplicadas recursivamente. La tabla de abajo lista las
cuatro llamadas que ocurren sobre una expresión, en el orden en que devuelven:
primero la hoja, de último la raíz. Diga qué entrega cada una antes de pasar a
la siguiente.
El match entra por el primer caso que coincide.
Los dos últimos son los que bajan a los hijos cuando ninguna regla aplica.
simplificar(Suma(Prod(Numero(1), Numero(5)), Prod(Numero(0), Numero(7))))
Las seis reglas están todas escritas, y aun así el
resultado sale a medias. Lo que decide no es cuántas reglas hay sino contra
qué se comparan: los patrones de la raíz miran a
Prod(Numero(0), Numero(7)), que no es Numero(0),
y la regla e + 0 = e queda descartada antes de que el cero
exista. Para cuando los hijos devuelven Numero(5) y
Numero(0), el match de la raíz ya terminó.
La versión que simplifica los hijos primero compara los patrones contra lo que ellos devolvieron, y con eso una pasada alcanza:
Sobre la misma expresión, simplificar devuelve
Suma(Numero(5),Numero(0)) y
simplificarDesdeLasHojas devuelve Numero(5).
Aplicar la primera dos veces, simplificar(simplificar(e)),
también da Numero(5): el segundo recorrido encuentra la suma
con el cero ya formada y entonces sí entra por su regla. El ejemplo que el
enunciado propone tiene la misma forma:
Suma(Prod(Numero(0), Numero(99)), Numero(5)) sale como
Suma(Numero(0),Numero(5)) en la primera pasada y como
Numero(5) en la segunda.
Dos detalles del recorrido. El Numero(7) nunca se visita:
la regla 0 * e = 0 devuelve el cero sin llamar
simplificar sobre el otro lado, y una rama entera se descarta
de un golpe. Y el valor no se mueve: eval de la expresión
original y de cualquiera de sus versiones simplificadas responde 5. Lo que
cambia es el árbol, no lo que vale.