← Volver a los ejercicios

simplificar: qué devuelve cada llamada

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

1. Las reglas y la función

e + 0 = e0 + e = e e * 1 = e1 * e = e e * 0 = 00 * e = 0

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

2. La tabla, de las hojas hacia la raíz

3. ¿Por qué una sola pasada de las reglas no basta, y qué hay que hacer para que sí?

4. Lo que se lleva de aquí

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.