Evaluación de árboles de expresiones aritméticas

Las expresiones aritméticas se pueden representar como árboles con números en las hojas y operaciones en los nodos. Por ejemplo, la expresión «9-2*4» se puede representar por el árbol

Definiendo el tipo de dato Arbol por

la representación del árbol anterior es

Definir la función

tal que (valor a) es el valor de la expresión aritmética correspondiente al árbol a. Por ejemplo,

Soluciones

Pensamiento

En cierto modo, las matemáticas no son el arte de responder preguntas matemáticas, es el arte de hacer las preguntas correctas, las preguntas que te dan una idea, las que te guían en direcciones interesantes, las que se conectan con muchas otras preguntas interesantes, las que tienen hermosas respuestas. ~ Gregory Chaitin

Problema de las puertas

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:

  • Inicialmente todas las puertas están cerradas.
  • El primer camarero cambia de estado las puertas de todas las habitaciones.
  • El segundo cambia de estado de las puertas de las habitaciones pares.
  • El tercero cambia de estado todas las puertas que son múltiplos de 3.
  • El cuarto cambia de estado todas las puertas que son múltiplos de 4
  • Así hasta que ha pasado el último camarero.

Por ejemplo, para n = 5

Los estados de las puertas se representan por el siguiente tipo de datos

Definir la función

tal que (final n) es la lista de los estados de las n puertas después de que hayan pasado los n camareros. Por ejemplo,

Soluciones

Pensamiento

… cuánto exilio en la presencia cabe.

Antonio Machado

Simplificación de expresiones booleanas

El siguiente tipo de dato algebraico representa las expresiones booleanas construidas con una variable (X), las constantes verdadera (V) y falsa (F), la negación (Neg) y la disyunción (Dis):

Por ejemplo, la fórmula (¬X v V) se representa por (Dis (Neg X) V).

Definir las funciones

tales que (valor p i) es el valor de la fórmula p cuando se le asigna a X el valor i. Por ejemplo,

y (simplifica p) es una expresión obtenida aplicándole a p las siguientes reglas de simplificación:

Por ejemplo,

Comprobar con QuickCheck que para cualquier fórmula p y cualquier booleano i se verifica que (valor (simplifica p) i) es igual a (valor p i).

Para la comprobación, de define el generador

que usa las funciones liftM y liftM2 de la librería Control.Monad que hay que importar al principio.

Soluciones

Pensamiento

¿Dices que nada se pierde?
Si esta copa de cristal
se me rompe, nunca en ella
beberé, nunca jamás.

Antonio Machado

Mínimo número de operaciones para transformar un número en otro

Se considera el siguiente par de operaciones sobre los números:

  • multiplicar por dos
  • restar uno.

Dados dos números x e y se desea calcular el menor número de operaciones para transformar x en y. Por ejemplo, el menor número de operaciones para transformar el 4 en 7 es 2:

y el menor número de operaciones para transformar 2 en 5 es 4

Definir las siguientes funciones

tales que

  • (arbolOp x n) es el árbol de profundidad n obtenido aplicándole a x las dos operaciones. Por ejemplo,

  • (minNOp x y) es el menor número de operaciones necesarias para transformar x en y. Por ejemplo,

Soluciones

Pensamiento

¿Dijiste media verdad?
Dirán que mientes dos veces
si dices la otra mitad.

Antonio Machado

Expresiones aritméticas generales

Las expresiones aritméticas. generales se contruyen con las sumas generales (sumatorios) y productos generales (productorios). Su tipo es

Por ejemplo, la expresión (2 * (1 + 2 + 1) * (2 + 3)) + 1 se representa por S [P [N 2, S [N 1, N 2, N 1], S [N 2, N 3]], N 1]

Definir la función

tal que (valor e) es el valor de la expresión e. Por ejemplo,

Soluciones

Pensamiento

Vivir es devorar tiempo, esperar; y por muy trascendente que quiera ser nuestra espera, siempre será espera de seguir esperando.

Antonio Machado