Más diversión con tipos algebraicos

En otra entrada comenté la elegancia de los tipos de datos algebraicos (ADT) y como este simple concepto reemplaza a las enumeraciones, estructuras y uniones de otros lenguajes. Adicionalmente, los ADT ofrecen otra característica interesante: el emparejamiento de patrones (pattern matching).

En principio, los elementos de un ADT solo pueden ser accedidos por medio del emparejamiento de patrones. Veamos un ejemplo con un tipo de datos lista:

data Lista a = Nulo | Cons a (Lista a)

lista1 = Nulo
lista2 = Cons 3 Nulo
lista3 = Cons 7.3 (Cons 4.0 Nulo)

Nota como el tipo de datos Lista es polimórfica (define listas de enteros, reales o cualquier otro tipo) y recursiva (una lista de tipo a esta formada por un valor de tipo a unida a una lista de tipo a).

Los valores de tipo Lista están compuestos, o bien por el valor Nulo, o bien por un par ordenado "marcado" por Cons, cuyo primer elemento es de tipo a y su segundo es de tipo Lista a. Estos dos "marcadores" forman la base para el emparejamiento de patrones. Por ejemplo, para calcular la longitud de una lista:

longitud Nulo = 0
longitud Cons a b = 1 + longitud b

Estas dos lineas combinadas, forman la definición de la función longitud. Utilizamos la primera solamente cuando se invoca longitud con la lista vacia (valor Nulo) y la segunda en los otros casos (valor Cons).

Una ventaja del emparejamiento de patrones, es que podemos ver con claridad cuando nuestras funciones manejan todos los casos posibles. El compilador puede advertirnos cuando obviemos alguno.

Adicionalmente, como dividimos nuestra función longitud en dos expresiones, resulta más fácil de leer. Podemos concentrarnos en las peculiaridades de cada patrón por separado.

Cabe destacar que el emparejamiento de patrones se puede usar también para separar casos de acuerdo a los valores dentro de los ADT, no solo por sus "marcadores". Por ejemplo, la función elem que devuelve el i-simo elemento de una lista:

elem 0 (Cons a b) = a
elem i (Cons a b) = elem (i-1) b

En este caso, solo aplicamos la primera expresión cuando pidamos el elemento cero de una lista.