top of page

6 Clases Case y comparación por patrones

 


Un tipo de estructura frecuente en aplicaciones es la de árbol. Por ejemplo, los intérpretes y los compiladores normalmente representan internamente a los programas como árboles; los documentos XML son árboles; y muchos tipos de contenedores
están basados en árboles, como por ejemplo los árboles rojo/negro.


Examinaremos ahora como representar y manipular estos árboles es Scala a través de un pequeño programa calculadora. El propósito del programa es manipular expresiones aritméticas muy simples formadas por sumas, enteros y variables. Dos
ejemplos de tales expresiones son 1+2 y (x +x)Å(7+y).


Primero tenemos que decidir una manera de representar este tipo de expresiones. LA forma más natural es un árbol, cuyos nodos son operaciones(en este caso la suma) y cuyas hojas son valores(aquí constantes o variables). En Java, se podría representar este árbol usando una superclase abstracta para los árboles y una subclase concreta para nodo u hoja. En un lenguaje de programación funcional, uno podría usar para el mismo propósito un tipo de dato algebraico.


Scala proporciona el concepto de clases case que de algunamanera es algo intermedio entre los dos. Aquí está como se pueden usar para definir el tipo de los árboles de nuestro ejemplo:
 

abstract class Arbol
    case class Sum(l: Arbol, r: Arbol) extends Arbol
    case class Var(n: String) extends Arbol
    case class Const(v: int) extends Arbol


El hecho de que las clases Sum, Var y Const sean declaradas como clases case significa que son diferentes de las clases estándar en varios aspectos:


• la palabra clave new no es obligatoria para crear instancias de estas clases (es decir, podemos escribir Const(5) en vez de new Const(5)),
 

• automáticamente se definen funciones de acceso a los parámetros del constructor( es decir, es posible obtener el valor del parámetro del contructor v de una instancia c de la clase Const simplemente escribiendo c.v),
 

• se proporciona definición por defecto para los métodos equals y hashCode, que funcionan sobre la estructura de las instancias y no sobre su identidad,
 

• se proporciona una definición por defecto para el método toString, que escribe el valor en “formato fuente (source form)” (es decir, el árbol de la expresión x +1 se escribe como Sum(Var(x),Const(1))),
 

• se pueden diferenciar instancias de estas clases mediante concordancia con patrones(pattern matching) como veremos posteriormente.
 

 

Una vez que hemos definido el tipo de datos con el que representar nuestras expresiones aritméticas podemos comenzar a definir operaciones con las que manipularlas. Empezaremos con una función para evaluar una expresión dentro de un
entorno. El propósito del entorno es el de proporcionar valores a las variables. Por ejemplo, la expresión x+1 evaluada en un entorno que asocia el valor 5 a la variable x, escrito {x !5}, da como resultado 6.


Por tanto tenemos que encontrar una manera de representar entornos. Podríamos hacerlo claro está usando algún tipo de estructura de datos asociativa como una tabla hash, pero también podemos ¡usar funciones directamente!. En realidad un
entorno no es más que una función que asocia un valor a un nombre(de variable). El entorno {x !5} de antes puede ser escrito fácilmente en Scala así:


{ case "x" => 5 }
 

 

Está notación define una función que, cuando recibe la cadena de texto "x" como argumento, devuelve el entero 5, en cualquier otro caso falla con una excepción. Antes de escribir la función de evaluación, demos un nombre al tipo de datos de los entornos. Podríamos usar siempre el tipo String => int para los entornos, pero nuestro programa se simplifica si introducimos un nombre para este tipo de dato, y además así los posibles cambios futuros serán más fáciles de realizar. Esto se consigue en Scala usando la siguiente notación:


type Entorno = String => int
 

 

A partir de ahora, el tipo Entorno se puede usar como un alias del tipo de funciones de String a int. Podemos ahora dar la definición de la función de evaluación. Conceptualmente es muy simple: el valor de la suma de dos expresiones es simplemente la suma del valor de esas expresiones; el valor de una variable se obtiene directamente del entorno; y el valor de una constante es la propia constante. Expresar esto en Scala no es mucho más dificil:


def eval(t: Arbol, ent: Entorno): int = t match {
    case Sum(l, r) => eval(l, ent) + eval(r, ent)
    case Var(n) => env(n)
    case Const(v) => v
}


Esta evaluación funciona realizando comparación de patrones(pattern matching) sobre el árbol t. Intuitivamente el significado de la definición anterior debería quedar claro:


1. primero se comprueba si el árbol t es de tipo Sum, y si lo es, asigna el subárbol izquierdo a una variable llamada l, el sub-árbol derecho a una variable llamada r y luego procede a evaluar la expresión al otro lado de la flecha; esta expresión puede(y lo hace) hacer uso de la asignación de variables hecha en el patrón que aparece a la izquierda de la flecha, es decir l y r,


2. si la primera comprobación no se cumple, es decir el árbol no es un Sum, continúa y comprueba si t es de tipo Var; si lo es, asigna el nombre que contiene el nodo Var a la variable n y pasa a la expresión de la derecha,
 

3. si la segunda comprobación también falla, es decir si t no es ni Sum ni Var, comprueba si es Const, y si lo es, asigna el valor que haya en el nodo Const a la variable v y prosigue con el lado derecho,
 

4. por último, si todas las comprobaciones fallan, se lanza una excepción para señalar el fallo en la concordancia de la expresión con los patrones con los que se compara. Lo que aquí sólo podría pasar si se declararan más sub-clases de Arbol.
 

Vemos que la idea básica de la concordancia con patrones es intentar comparar un valor con una serie de patrones, y en cuanto un patrón encaja, extraer y nombrar varias partes del valor, para finalmente evaluar código que típicamente utiliza esas partes recién nombradas.


Un programador curtido en orientación a objetos podría preguntarse porque no hemos definido eval como un método de la clase Arbol y de sus subclases. En realidad se podría haber hecho así puesto que Scala permite definir métodos en clases-case igual que en cualquier otra clase normal. Decidir cuando usar patrones o cuando usar métodos es en realidad una cuestión de gustos, pero también hay implicaciones importantes sobre extensibilidad:


• cuando se usan métodos, es fácil añadir un nuevo tipo de nodo puesto que basta con definir la subclase de Arbol correspondiente; pero por otro lado, añadir una operación nueva para manipular el arbol es tedioso puesto que requiere la modificación de todas las subclases de Arbol,
 

• cuando se usa concordancia de patrones la situación se invierte: añadir un nuevo tipo de nodo requiere modificar todas las operaciones que comparan patrones contra el árbol para que tengan en cuenta el nuevo tipo de nodo; por otro lado, añadir una nueva operación es fácil, definiendola simplemente como una función independiente.
 

 

Para explorar en mayor profundidad la concordancia con patrones, definamos otra operación sobre operaciones aritméticas: la derivada simbólica. El lector seguramente recordará las reglas relativas a esta operación:
 

1. la derivada de una suma es la suma de sus derivadas,
 

2. la derivada de una variable v es uno si v es la variable respecto a la que se
deriva, y cero en otro caso,

 

3. la derivada de una constante es cero.
Estas reglas se pueden traducir a código Scala casi literalmente, para obtener la
siguiente definición:

 

def deriva(t: Arbol, v: String): Arbol = t match {
    case Sum(l, r) => Sum(deriva(l, v), deriva(r, v))
    case Var(n) if (v == n) => Const(1)
    case _ => Const(0)
}


Esta función introduce dos nuevos conceptos relacionados con la comparación con patrones. En primer lugar la expresión case para las variables tiene un requisito, una expresión seguida de la palabra clave if. Este requisito previene que la concordancia
con el patrón tenga éxito a menos que la expresión se cumpla. Aquí se usa para asegurarnos de que devolvemos la constante 1 sólo si el nombre de la variable que estamos derivando es el mismo que la variable de la derivada, v. La segunda funcionalidad nueva de la comparación con patrones que usamos aquí es el comodín(o wild-card), escrito como _, que es un patrón que concuerda con cualquier valor, sin tener que darle un nombre.


Aún no hemos explorado toda la potencia que nos proporciona la comparación con patrones, pero lo dejamos en este punto para mantener la brevedad de este documento. Pero todavia queremos ver como funcionan las dos funciones anteriores con un ejemplo real. Para este propósito, escribamos una función main simple que realice varias operaciones sobre la expresión (x+x)+(7+y): Primero calcula su valor en el entorno {x !5, y !7}, y luego calcula sus derivadas respecto a x y respecto a y.


def main(args: Array[String]) {
    val exp: Arbol = Sum(Sum(Var("x"),Var("x")),Sum(Const(7),Var("y")))
    val ent: Entorno = { case "x" => 5 case "y" => 7 }
    println("Expresión: " + exp)
    println("Evaluamos siendo x=5, y=7: " + eval(exp, ent))
    println("Derivada respecto a x:\n " + deriva(exp, "x"))
    println("Derivada respecto a y:\n " + deriva(exp, "y"))
}

 


Al ejecutar este programa se obtiene la salida esperada:

Expresión:

 

Sum(Sum(Var(x),Var(x)),Sum(Const(7),Var(y)))
 

Evaluamos siendo x=5, y=7: 24
 

Derivada respecto a x:
 

12
 

Sum(Sum(Const(1),Const(1)),Sum(Const(0),Const(0)))
 

Derivada respecto a y:
 

Sum(Sum(Const(0),Const(0)),Sum(Const(0),Const(1)))
 

Si examinamos la salida del programa, vemos que el resultado de la derivada debería simplificarse antes de mostrarlo al usuario. Definir una función de simplificación básica usando comparación con patrones es un problema interesante(aunque
sorprendentemente complicado), que se deja como ejercicio al lector.

bottom of page