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

     - 
    / \
   9   *
      / \
     2   4

Definiendo el tipo de dato Arbol por

   data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

la representación del árbol anterior es

   N (-) (H 9) (N (*) (H 2) (H 4))

Definir la función

   valor :: Arbol -> Int

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

   valor (N (-) (H 9) (N (*) (H 2) (H 4)))    ==  1
   valor (N (+) (H 9) (N (*) (H 2) (H 4)))    ==  17
   valor (N (+) (H 9) (N (div) (H 4) (H 2)))  ==  11
   valor (N (+) (H 9) (N (max) (H 4) (H 2)))  ==  13

Soluciones

data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol
 
valor :: Arbol -> Int
valor (H x)     = x
valor (N f i d) = f (valor i) (valor d)

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