Resolviendo problemas de forma funcional

Pensar de forma funcional es bastante difícil y más que nada si estamos programando en otro paradigma. Por lo tanto la idea es plantear un problema y buscar una solución funcional.

Problema Normalmente cuando escribíamos expresiones matemáticas en la escuela lo hacíamos de forma infija. Por ejemplo, 10 -(4 + 3) * 2. +, * y - son operadores infijos. Resulta bastante útil, ya que nosotros, como humanos, podemos analizar fácilmente estas expresiones. Lo malo es que tenemos que utilizar paréntesis para especificar la precedencia.

La Notación polaca inversa (RPN) es otra forma de escribir expresiones matemáticas. Al principio parece un poco complicado, pero en realidad es bastante fácil de entender y utilizar ya que no hay necesidad de utilizar paréntesis y muy fácil de utilizar en la calculadoras. Aunque las calculadoras más modernas usan una notación infija, todavía hay gente que lleva calculadoras RPN (del inglés, Reverse Polish Notation). Así se vería la expresión infija anterior en RPN:

10 4 3 + 2 * -

¿Cómo calculamos el resultado de esto? Bueno, piensa en una pila. Recorremos la expresión de izquierda a derecha. Cada vez que encontramos un número, lo apilamos. Cuando encontramos un operador, retiramos los dos números que hay en la cima de la pila, utilizamos el operador con ellos y apilamos el resultado de nuevo. Cuando alcancemos el final de la expresión, debemos tener un solo número en la pila si la expresión estaba bien formada, y éste representa el resultado de la expresión.

Si no estas pensando en Lisp, no tuviste infancia o tuviste una infancia feliz. En Lisp, el primer elemento de cada expresión es un operador y el resto de elementos son tratados como datos. Esta forma se denomina notación prefija o notación Polaca Cambridge. Lisp no utiliza la notación polaca inversa, usa la notación prefija de esta forma tampoco es necesario especificar la precedencia.

Pero sigamos con el problema, vamos a pensar en como podríamos hacer que una función tomara como parámetro una cadena que contenga una expresión RPN, como 10 4 3 + 2 * -, y nos devolviera el resultado.

Solución

Antes que nada para trabajar más cómodos necesitamos una lista que contenga los operadores y operandos, por lo tanto debemos tomar la cadena “10 4 3 + 2 * -” y separarla por los espacios y luego llevarla a una lista.

Cuando implementemos la solución de un problema, a veces es bueno ver como lo solucionamos de forma manual para ver si podemos sacar algo que nos ayude. Por lo tanto vamos a resolver la expresión “10 4 3 + 2 * -” de forma manual.

Como dijimos anteriormente llevamos “10 4 3 + 2 * -” a una lista. Luego tomamos el primer elemento y lo apilamos de forma que ahora nuestra pila contiene un 10. El siguiente elemento es un 4, así que lo apilamos también. La pila ahora contiene 10, 4. Hacemos los mismo para el 3 y conseguimos una pila que contiene 10, 4, 3. Ahora, encontramos un operador, +. Retiramos los dos números que se encuentran en la cima de la pila (de forma que la pila se quedaría de nuevo solo con 10), sumamos esos dos números y apilamos el resultado. La pila contiene 10, 7 ahora mismo. Apilamos 2 y obtenemos 10, 7, 2. Multiplicamos 7 y 2 y obtenemos 14, así que lo apilamos y la pila ahora contendrá 10, 14. Para terminar hay un -. Retiramos 10 y 14 de la pila, restamos 14 a 10 y apilamos el resultado. El número que contiene la pila es -4 y como no hay más números ni operadores en la expresión, ese es el resultado.

¿Qué fue lo hicimos? Recorrimos la expresión de izquierda a derecha mientras manteníamos una pila.

Lo primero que podemos pensar es en los casos especiales, ¿que deberíamos hacer si la lista de operadores y operandos esta vacía? En ese caso deberíamos devolver la pila, la pila debería tener un elemento, pero esta validación escapa del ejercicio. Si tiene un elemento debemos analizar que es ese elemento si es un operador debemos tomar los dos elementos de la pila, luego aplicar el operador y por ultimo apilar el resultado. Si es un operando debemos simplemente apilarlo.

Una cosa más que tenemos que pensar es, bueno ¿Cómo vamos a representar la pila? Propongo que utilicemos una lista. También propongo que mantengamos en la cabeza de la lista la cima de la pila. De esta forma añadir un elemento en la cabeza de la lista es mucho más eficiente que añadirlo al final. Así que si tenemos una pila como, 10, 4, 3, la representaremos con una lista como [3,4,10].

Ahora tenemos suficiente información para bosquejar vagamente nuestra función. Tomará una cadena como "10 4 3 + 2 * -" y la romperá en una lista de elementos utilizando words de forma que obtenga ["10","4","3","+","2","*","-"]. Luego, utilizará un pliegue por la izquierda sobre esa lista y generará una pila con un único elemento, como [-4]. Tomará ese único elemento de la lista y ese será nuestro resultado final.

Veamos el código en scala:

//Paso la cadena a una lista  
val valores = "10 4 3 + 2 * -".split(" +").toList
   
   
 def eval(valores : List[String], pila:List[String]) : List[String] = valores match {
    case Nil => pila
    case x :: xs => x match {
      case "+" => eval(xs, (pila(1).toInt + pila.head.toInt).toString :: pila.tail.tail)
      case "-" => eval(xs, (pila(1).toInt - pila.head.toInt).toString :: pila.tail.tail)
      case "*" => eval(xs, (pila(1).toInt * pila.head.toInt).toString :: pila.tail.tail)
      case _ => eval(xs, x :: pila )
    }
}   

eval(valores, Nil)                            
// res0: List[String] = List(-4)

Como podemos ver usando funciones recursivas podemos recorrer la lista con operadores y operandos.

Otra forma de recorrer una lista muy fácilmente es por medio de los pliegues. Con los pliegues podemos implementar cualquier función que recorra una lista de izquierda a derecha, elemento a elemento, y genere (o acumule) un resultado.

En este caso, vamos a utilizar un pliegue por la izquierda, ya que vamos a recorrer la lista de izquierda a derecha.

Veamos la solución con pliegues:

def eval2(pila:List[String], x: String) : List[String] = x match {
      case "+" =>  (pila(1).toInt + pila.head.toInt).toString :: pila.tail.tail
      case "-" =>  (pila(1).toInt - pila.head.toInt).toString :: pila.tail.tail
      case "*" =>  (pila(1).toInt * pila.head.toInt).toString :: pila.tail.tail
      case _ => x :: pila
}                                                
 
 
valores.foldLeft(List[String]()) (eval2)         
//> res1: List[String] = List(-4)

o la versión resumida usando clausuras:

"10 4 3 + 2 * -".split(" +").toList.foldLeft(List[String]()) ((pila:List[String], x: String) => x match {
      case "+" =>  (pila(1).toInt + pila.head.toInt).toString :: pila.tail.tail
      case "-" =>  (pila(1).toInt - pila.head.toInt).toString :: pila.tail.tail
      case "*" =>  (pila(1).toInt * pila.head.toInt).toString :: pila.tail.tail
      case _ => x :: pila
}) 

Como ven podemos resolver el problema utilizando pattern matching y pliegues o funciones recursivas.