Clase 5. Reconocimiento de patrones¶
Jueves 8 de octubre de 2026.
Un conjunto de enteros se puede guardar como un árbol binario de búsqueda, y
ese árbol tiene exactamente dos formas: o está vacío, o es un elemento con dos
hijos. La sesión parte de ahí y recorre dos maneras de escribir esa
distinción, la jerarquía de clases y el match sobre la forma, hasta llegar
a los tipos sellados, donde el compilador avisa si falta un caso.
Las diapositivas están en el Campus Virtual. Los diez ejercicios interactivos de la sesión están en Ejercicios.
Referencia: Odersky, Spoon y Venners, Programming in Scala, 3.ª edición, capítulos 10, 12 y 15.
Un conjunto como árbol¶
La especificación es corta: insertar devuelve un conjunto con el elemento, y
pertenece dice si está. La clase que la declara no se puede instanciar,
porque no hay un «conjunto genérico», así que es abstracta:
abstract class ConjEnt {
def insertar(x: Int): ConjEnt
def pertenece(x: Int): Boolean
}
Las dos formas la implementan. El vacío responde que no a todo:
Vacio.pertenece(x) false, para cualquier x
y no por descuido: sobre el conjunto vacío, x pertenece es falso para todo
x, porque no hay elementos. El no vacío compara contra su elemento y baja al
hijo que corresponde; si el elemento ya está, insertar devuelve el mismo
conjunto, porque un conjunto no repite.
Nada se modifica: cada inserción construye un árbol nuevo.
Despacho dinámico¶
conj.pertenece(7) no dice qué código corre. Lo decide el objeto que recibe la
llamada: si es un vacío, la versión que devuelve false; si es un nodo, la que
compara y baja. Eso es polimorfismo, y la forma concreta se llama despacho
dinámico: el método se resuelve según el objeto, no según el tipo escrito.
Sobre un nodo que guarda el 7, pertenece(7) pregunta dos veces: ¿7 es menor
que 7? No. ¿Es mayor? Tampoco. Entonces es él, y responde true.
Implementar, sobreescribir y el objeto único¶
Una clase hija implementa lo que la madre dejó sin cuerpo, y
sobreescribe, con override, lo que la madre ya traía escrito.
El vacío no guarda nada: no tiene campos y todas sus instancias serían
idénticas. Para eso está object:
object Vacio extends ConjEnt
Hay una sola instancia en todo el programa y se usa sin new. Es el mismo
mecanismo del main, que es el punto de entrada y por eso no se instancia.
Toda clase que no declara de quién hereda, hereda de Object, la raíz. De ahí
viene equals, y de ahí viene un tropiezo conocido: dos objetos Persona con
el mismo nombre y la misma edad son distintos para == mientras nadie
sobreescriba equals, porque lo que se compara es la referencia y no los
campos.
Traits¶
Scala tiene herencia simple: una clase extiende una sola. Para compartir comportamiento que cruza jerarquías están los traits, que son lo que en Java son las interfaces, con una diferencia: un trait sí puede traer métodos ya implementados.
trait Plano { def alto: Int; def ancho: Int; def area: Int = alto * ancho }
trait Movible { def mover(dx: Int, dy: Int): Rectangulo }
class Rectangulo(...) extends Plano with Movible
Rectangulo(en 0,0; 3x4)
12
Rectangulo(en 10,5; 3x4)
El area del trait lo hereda el rectángulo sin escribirlo, y mover devuelve
un rectángulo nuevo.
Por qué no hay herencia múltiple. Con tres padres que a su vez tienen tres
padres, buscar un método se vuelve una explosión; y si dos padres definen
mover, no hay forma de decidir. Python resuelve tomando el primero en el
orden de herencia, y aun así el problema sigue ahí.
Cuándo cada uno. Clase abstracta cuando hay una jerarquía clara y hace falta un constructor con parámetros. Trait para comportamiento transversal, que se mezcla en clases que no comparten ancestro.
Reconocimiento de patrones¶
Hasta aquí, preguntar por la forma del dato obliga a algo así:
if (conj.isInstanceOf[NoVacio]) {
val elem = conj.asInstanceOf[NoVacio].elem
...
}
El match hace las dos cosas de una vez: distingue la forma y saca los campos.
def listaEnteros(conj: ConjEnt): List[Int] = conj match {
case Vacio() => List()
case NoVacio(elem, izq, der) => listaEnteros(izq) ++ List(elem) ++ listaEnteros(der)
}
case NoVacio(elem, izq, der) no compara contra nada: nombra las tres partes
para usarlas en el cuerpo. Y ++ concatena listas.
Sobre el árbol con 10 en la raíz, 8 a la izquierda (con 6 y 9) y 15 a la derecha (con 13 y 16):
List(6, 8, 9, 10, 13, 15, 16)
Sale ordenado porque el recorrido va izquierda, raíz, derecha: eso es el
recorrido en orden. Poniendo List(elem) al principio queda preorden;
al final, postorden.
El _ cubre lo que no casó, como el default de un switch. Los patrones que
aparecen en el curso son constantes, valores con su tipo, tuplas, la forma
cabeza :: cola de una lista, y el comodín.
Listas¶
Una lista es una colección de elementos del mismo tipo, y se construye de dos maneras que dan lo mismo:
scala> List(1, 2, 3)
val res0: List[Int] = List(1, 2, 3)
scala> 1 :: 2 :: 3 :: Nil
val res1: List[Int] = List(1, 2, 3)
Nil es la lista vacía y cierra toda construcción con ::. De una lista se
piden dos cosas: head, el primer elemento, y tail, el resto.
scala> val l = List(1, 2, 3, 4)
scala> l.head 1
scala> l.tail List(2, 3, 4)
scala> l.tail.head 2
scala> l.tail.tail.tail.tail List()
El segundo elemento es l.tail.head y el tercero l.tail.tail.head. Scala
permite además l(2), que devuelve el tercero, y en este curso no se usa:
indexar es recorrer con un índice, que es la forma imperativa. Una lista se
recorre con head y tail.
Sumar una lista, tres veces¶
Recursión lineal:
def sumarLista(l: List[Int]): Int =
if (l.isEmpty) 0 else l.head + sumarLista(l.tail)
Recursión de cola, con acumulador y @tailrec:
def sumarLista(l: List[Int]): Int = {
@tailrec
def auxiliar(l: List[Int], acc: Int): Int =
if (l.isEmpty) acc else auxiliar(l.tail, acc + l.head)
auxiliar(l, 0)
}
Y con match, que es la misma idea escrita sobre la forma:
def sumarLista(l: List[Int]): Int = l match {
case Nil => 0
case x :: xs => x + sumarLista(xs)
}
Las tres dan 6 sobre List(1, 2, 3). El caso base es siempre la lista vacía, y
se llega a ella aplicando tail las veces que haga falta.
Tipos sellados y case classes¶
Un árbol de expresiones aritméticas se puede intentar con un solo tipo que cargue banderas:
def esNumero: Boolean
def esSuma: Boolean
def esProducto: Boolean
def valor: Int
def opIzq: Expr
def opDer: Expr
y entonces Numero responde true a la primera, false a las otras dos, y
lanza un error si alguien le pide operandos. Funciona, y agregar la división
obliga a tocar todas las clases para añadir esDiv.
La alternativa declara las formas y nada más:
sealed trait Expr
case class Numero(valor: Int) extends Expr
case class Suma(e1: Expr, e2: Expr) extends Expr
case class Prod(e1: Expr, e2: Expr) extends Expr
case class da el constructor sin new, la comparación por campos y el patrón
para el match. sealed cierra la jerarquía: todas las formas están en este
archivo, así que el compilador avisa cuando un match deja un caso por
fuera. Esa advertencia es la que no existe con las banderas booleanas.
Las operaciones quedan afuera, cada una un match:
def eval(e: Expr): Int = e match {
case Numero(n) => n
case Suma(a, b) => eval(a) + eval(b)
case Prod(a, b) => eval(a) * eval(b)
}
mostrar(Suma(Numero(3), Prod(Numero(2), Numero(5)))) 3 + 2 * 5
eval(...) 13
eval(Div(Suma(Numero(10), Numero(2)), Resta(Numero(6), Numero(3)))) 4
mostrarConParentesis(Prod(Suma(Numero(1), Numero(2)), Numero(4))) (1 + 2) * 4
El 13 sale de evaluar primero el producto, 10, y sumarle 3. Y los paréntesis de
la última línea no están en el dato: los pone mostrarConParentesis al bajar
por cada operación compuesta.
El ejercicio de la sesión¶
Un robot en una cuadrícula, con el modelo de datos ya dado: Direccion con las
cuatro, Orden con Avanzar(n), Girar(sentido), Repetir(n, orden) y
Secuencia(ordenes), y un Estado(x, y, direccion) que arranca en el origen
mirando al norte.
ejecutar(inicial, Avanzar(3)) (0, 3) norte
Secuencia(Avanzar(2), Girar(Derecha), Avanzar(4)) (4, 2) este
Repetir(4, Secuencia(Avanzar(1), Girar(Derecha))) vuelve al origen
Avanzar(-2) (0, -2) norte
Repetir(0, Avanzar(5)) no se mueve
Después, dos funciones que se escriben con match sobre la orden:
cuentaBasicas, que da 1 para una orden básica y suma las de adentro, de modo
que el cuadrado da 8; y profundidad, que da 1 para una básica y 1 más el
máximo de lo que contenga: Avanzar(3) es 1, una secuencia de básicas es 2, y el
cuadrado, 3.
Lo que queda¶
Las listas apenas se abrieron aquí: el recorrido con head y tail y el
patrón x :: xs. Lo que sigue es construirlas y operarlas, insertando,
aplanando y agrupando en corridas, y después las tuplas, el ordenamiento por
mezcla y las
funciones de alto orden sobre listas.