Apuntes de

Alberto Ruiz, (aruiz@[Link])

January 6, 2007

1 Introducción

Lo mejor serı́a olvidarse de este documento e irse directamente a la página web de la comunidad Haskell, donde podemos
encontrar toda la información y material que podamos necesitar: tutoriales, ejemplos de código, etc:

[Link]

La programación funcional es sobre todo una forma más divertida de programar. Su caracterı́stica más importante es la
transparencia referencial: lo que se ve es lo que hay; nada depende de un ‘estado’ de la máquina. No hay variables
ni asignaciones sino aplicación de funciones sobre el resultado de la aplicación de funciones, etc., donde los argumentos
son datos ‘normales’ u otras funciones (son first class citizens del lenguaje). En lugar de la iteración se usa bastante la
recursión apoyada en listas.

Esto contrasta mucho con los lenguajes imperativos, sobre cuyo código difı́cil razonar, ya que consiguen su objetivo como
un efecto colateral de las asignaciones de memoria de un lado para otro. Aquı́ damos definiciones casi matemáticas, en las
hay verdaderas igualdades, porque podemos sustuir libremente un lado de la igualdad por otro en todo el código (equational
reasoning) sin cambiar el resultado del programa. Curiosamente, esto también es bueno para los optimizadores de código
y para la paralelización. Además es posible simplificar automáticamente algunas expresiones. Es muy interesante leer
el paper Why functional programming matters (aunque utiliza una sintaxis ligeramente distinta a la de Haskell, pero
igualmente muy clara y comprensible).

Hay muchos lenguajes con inspiración funcional, cada uno con sus peculiaridades. El propio lenguaje de programación del
entorno de cálculo cientı́fico Mathematica, caracterizado por un notable poder expresivo, utiliza construcciones funcionales
y transformaciones de estructura definidas mediante pattern matching.

Haskell es un lenguaje desarrollado por la comunidad, de código abierto, multiplataforma, con varias implementaciones
que compiten ayudándose entre sı́. Hay un núcleo estable del lenguaje y muchas extensiones más o menos experimentales,
que si dan resultado tienden a incorporarse en versiones futuras. Está orientado tanto al campo académico como a su
uso en aplicaciones reales, y es una plataforma ideal para experimentación e investigación en aspectos avanzados de la
computación.

Uno de sus mayores ventajas es que se comprueba en tiempo de compilación la consistencia de tipos, de manera que se
reducen muchı́simo los errores en tiempo de ejecución. (Si se hacen bien las cosas se pueden evitar todos.) Y entonces
ocurre un fenómeno muy curioso, que es una de las razones por las que el lenguaje ‘engancha’: si el código compila,
entonces lo más seguro es que ¡funcione bien!.

En los lenguajes imperativos, por muy estricta que sea, la comprobación estática no puede verificar que el orden de las
operaciones es el correcto. En cambio, como en la programación funcional no hay orden, la consistencia estática es una
garantı́a mucho más fuerte de corrección. Incluso ayuda cuando has entendido mal el algoritmo, porque eso a veces
conduce a que los tipos del programa son inconsistentes. Esto lo explican mejor en Why Haskell just works.

Otra caracterı́stica importante es el polimorfismo: el lenguaje está diseñado para que las funciones sean capaces de admitir
todos los tipos de dato que admitan las operaciones utilizadas. Por eso, si escribimos una función de ordenación, funcionará

1
con cualquier tipo que admita comparaciones. Es como si estuvieramos programando todo el rato con ‘templates’ parecidas
a las de C++, pero con un verdadero control estático de consistencia de tipos y la posibilidad de compilar realmente esas
funciones polimórficas.

Además, el sistema es capaz de inferir el tipo más general de las funciones que aparecen en el programa. Normalmente,
para documentar el código se suele poner la signatura de las funciones más importantes. En cualquier caso, el compilador
deduce automáticamente el tipo más general de una función (y, como veremos más adelante, se lo podemos preguntar al
intérprete con :t fun).

La sintaxis está orientada a la claridad del código, lo que permite que muchos algoritmos (¿todos?) se expresen de forma
muy concisa. De hecho, podrı́amos afirmar que si el código queda bonito seguro que es correcto. Y si queda feo seguro
que se puede mejorar. Esa tremenda concisión y elegancia a veces hace pensar (epecialmente a programadores expertos en
otro tipo de lenguajes, en los que hay que estar pendiente de millones de detalles técnicos al escribir el código) que se trata
de un pseudolenguaje de juguete. Sin embargo, el hecho de que un algoritmo pueda escribirse de forma engañosamente
simple no significa que no haya un control muy estricto sobre él. Un código sencillo que pasa todos los tests de consistencia
es improbable que sea incorrecto. Un mismo concepto de programación se puede expresar de muchas formas distintas, a
gusto del programador, pero casi todo es ‘syntactic sugar’ que internamente se transforma en lambda cálculo con un cierto
sistema de tipos.

La evaluación es no estricta (lazy), lo que significa que las definiciones no se evalúan si no es estrictamente necesario para
obtener el resultado final. Esto nos permite entrar en un mundo nuevo de técnicas de programación mucho más potentes y
modulares.

Un concepto distintivo del lenguaje es de las clases de tipos. Esto no tiene nada que ver con la orientación a objetos (que
también se puede conseguir mediante ciertas técnicas de programación). Es una forma sistemática de abordar la sobrecarga
de funciones de forma no jerárquica.

La entrada/salida y la secuenciación de acciones se trata mediante un enfoque que también es novedoso, basado en la clase
de tipos monad, una abstracción que curiosamente resulta muy útil también en otros ámbitos. De hecho se podrı́a decir
que puedes escribir código en estilo imperativo mejor que en los lenguajes imperativos. . .

Finalmente, la modularización de los programas se consigue de forma muy sencilla, mediante la declaración explı́cita
de los sı́mbolos que exporta cada módulo. Los tipos abstractos de datos se consiguen sencillamente no exportando sus
‘constructores’ sino funciones que los crean manteniendo los invariantes deseados.

El poder expresivo del lenguaje facilita la existencia de bibliotecas muy interesantes (parsec, quickcheck, etc.) y, por
supuesto, podemos utilizar cualquier biblioteca externa (esencialmente a través de C) mediante el Foreign Function Inter-
face.

Los tutoriales de la página web nos explican en detalle el lenguaje ası́ que aquı́ solo pondremos ejemplos que nos den una
idea de cómo se hacen las cosas. Dos muy buenos son: A gentle introduction to Haskell y Yet another Haskell tutorial. Hay
más material en Learning Haskell. Aquı́ tenemos la definición completa del lenguaje y las bibliotecas: Haskell Report.
Finalmente es muy interesante leer “The history of Haskell” (cuando esté online). Mientras tanto se puede echar un vistazo
a esta retrospectiva.

Por supuesto no todo son ventajas. A veces se dice que no es tan rápido como C y en algoritmos de procesamiento intensivo
de datos, por supuesto esto es verdad. El precio que se paga por ascender en la capacidad de abstracción es una pérdida de
eficiencia, a veces bastante apreciable, en comparación con los bucles de C. Sin embargo, no siempre lo más importante
es el tiempo de ejecución. También hay que contabilizar el tiempo de desarrollo, de depuración, mantenimiento, y exten-
sibilidad de una aplicación (lo que explica el éxito de lenguajes como perl, python, ruby, etc.). En algunas aplicaciones,
pensemos por ejemplo en la criptografı́a, la corrección del código es más importante que la velocidad. Además, casi siem-
pre el 90% del tiempo de ejecución es responsabilidad de un 10% del código. Por lo que si necesitamos reescribir algún
proceso crı́tico en C, o utilizar una biblioteca optimizada externa (igual que lo que se hace en cualquier otro lenguaje,
cuando se engancha con blas+lapack, con OpenGL o con IPP), podemos hacerlo sin ningún problema. En cualquier caso,
coincido con la idea de que la ansiedad por las prestaciones conduce a la optimización prematura. Mejorar la eficiencia
del código ejecutable no deberı́a interferir siempre en la escritura de los algoritmos. Es una tarea de los diseñadores de
compiladores.

Un problema más serio es el de razonar sobre la complejidad espacial de los algoritmos, debido a la evaluación no estricta.
Pero hay herramientas de profiling que nos ayudan y nos dicen donde es conveniente, por ejemplo, forzar una evaluación
(seq) para que el problema se arregle.

2
En resumen, las decisiones de diseño de este lenguaje no tienen como máxima prioridad aprovechar al máximo la potencia
de cálculo del computador, sino ayudar al programador humano a escribir correctamente algoritmos cada vez más com-
plejos. Sobre esa base hay que juzgarlo. Y, ciertamente, no merece la pena aprender (o simplemente conocer) un lenguaje
que no cambia tus ideas sobre la programación. . . Aunque al final no se utilice en los proyectos ‘reales’, muchos de estos
conceptos pueden ayudarnos a programar mejor en cualquier otro lenguaje.

2 Compilador

Yo destacarı́a el compilador ghc (Glorious Glasgow Haskell Compiler), que siempre tiene las últimas mejoras del lenguaje.
Incluye un intérprete (ghci), lo cual es muy práctico para experimentar con el código. Otra alternativa muy buena es el
intérprete Hugs; y también hay otros compiladores más o menos experimentales.

2.1 Instalación

Todas las distribuciones de linux permiten instalar una versión bastante actualizada de ghc (or Hugs) mediante los re-
spectivos administradores de paquetes. Pero yo recomendarı́a la versión binaria más reciente de ghc (actualmente la 6.6),
que se puede instalar muy fácilmente como usuario local. Elegimos la versión generic Linux que encontramos en:

[Link] ghc [Link]#x86linux

desempaquetamos el tar.bz2 en cualquier sitio, hacemos ./configure y make-inplace. Añadiendo a PATH la ruta donde lo
hemos dejado, el compilador, el intérprete, y alguna otra utilidad más que luego veremos, funcionarán perfectamente. Para
comprobarlo nos vamos a cualquier otro directorio y en un terminal escribimos:
linux> ghc -V
The Glorious Glasgow Haskell Compilation System, version 6.6
linux>

2.2 Hello World

Para empezar a familiarizarnos con el sistema vamos a escribir el tı́pico programa que imprime Hello World!. En un
editor preparamos el siguiente programa (más adelante explicaremos la diferencia entre print y la función que usamos
aquı́):

main = putStrLn "Hola amigos"

Ahora lo compilamos y comprobamos su funcionamiento:

linux> ghc [Link] -o hello
linux> ./hello
Hola amigos

La compilación produce los archivos hello (el ejecutable), hello.o (código objeto), y [Link] (un ‘interface’ que
le viene bien para la compilación separada).

Una forma mejor de compilar es la siguiente:

linux> ghc [Link] --make -Wall -O

De esta forma se comprueba si hay que recompilar módulos y además incluye las directivas necesarias para usar tranquila-
mente todas las bibliotecas del sistema (podrı́amos hacer lo mismo con un makefile tı́pico y ghc -c, etc. En realidad muchas
veces viene bien tener un makefile y también usar --make, sobre todo cuando combinamos Haskell y C)

La opción -Wall no suele ser necesaria ya que avisa de cosas que no suelen importar mucho, por ejemplo que un nombre
oculta a otro, o que una función no tiene signatura (lo cual es normal, ya que el compilador la deduce él solito), o que una
función definida mediante pattern matching no cubre todos los casos (no es exhaustiva), lo que a veces sı́ es importante (se
nos ha olvidado) y a veces no (puede ser intencionado, ya que ese caso no puede producirse nunca).

3
La opción -O consigue un código que normalmente se ejecuta más rápido, pero, sobre todo, puede tener el efecto de que la
complejidad espacial de ciertas funciones sea la que realmente esperamos. Sin ella podrı́an implementarse ingenuamente
y ser intratables.

Ahora vamos a probar el intérprete. en un terminal tecleamos ghci. Deberı́a salir algo como:
linux> ghci
___ ___ _
/ _ \ /\ /\/ __(_)
/ /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98.
/ /_\\/ __ / /___| | [Link]
\____/\/ /_/\____/|_| Type :? for help.

Loading package base ... linking ... done.

Prelude> 2+2
4
Prelude>

Podemos probar el programilla anterior desde el intérprete:

Prelude> :l [Link]
k, modules loaded: Main.
Prelude Main> main
Hola amigos
Prelude Main> ˆD
linux>

Un proceso tı́pico es escribir las funciones en un fichero, probarlas en en intérprete, si hay que mejorarlas se hace :r eload,
hasta que todo vaya bien, y luego se termina ya el programa real con entrada/salida, opciones, etc. Por cierto, también
podemos ejecutar un programa fuente directamente mediante la utilidad runhaskell:
linux> runhaskell [Link]
Hola amigos

Y también usando #!/usr/bin/runhaskell para indicar un intérprete a bash, como cualquier lenguaje de scripts
(perl, python, ruby, etc.). Por ejemplo, el siguiente guión invierte el orden de todas las lı́neas recibidas por la entrada
estándard:

#! /home/brutus/apps/ghc-6.6/bin/i386-unknown-linux/runhaskell

f = reverse

main = interact (unlines . map f . lines)

Para ver si funciona se lo aplicamos a él mismo:

linux> cat [Link] | ./[Link]
lleksahnur/xunil-nwonknu-683i/nib/6.6-chg/sppa/suturb/emoh/ !#

esrever = f

)senil . f pam . senilnu( tcaretni = niam

linux>

Algunos comandos de unix pueden expresarse de manera muy simple en Haskell:

[Link] unix tools

2.3 Bibliotecas

La suite ghc incluye un conjunto muy amplio de bibliotecas, algo ası́ como la biblioteca estándar de Haskell, junto con
algunas otras también muy útiles (OpenGL, etc.) Para buscar en ellas podemos usar la documentación html generada
automáticamente por la herramienta Haddock (el doxygen de Haskell):

4
/home/brutus/apps/ghc-6.6/share/html/[Link]

o usar una herramienta muy práctica llamada Hoogle, a la que le puedes preguntar por el nombre (aproximado) o la sig-
natura (aproximada) de la función y te devuelve funciones que podrı́an ser la que buscas, con enlaces a la documentación:

[Link]

Hoogle puede instalarse en firefox como otro motor de búsqueda más.

Aquı́ están definidas, con ejemplos de uso, las funciones más utilizadas: Tour of the standard prelude.

Y esto es un motor en la web capaz de varias cosas: lambdabot.

2.4 Eficiencia

Es conveniente que nos hagamos una idea de la eficiencia que podemos conseguir en un ejemplito sencillo comparando
con C. Consideremos el siguiente programa que calcula una especie de sucesión de Fibonacci módulo 13:

#include <stdio.h>

int main(int argc, char* argv[]) {

int a = 1, b = 1, n, j, z;
n = atoi(argv[1]);
for(j = 3; j<=n; j++) {
z = (a + b)%13;
a = b;
b = z;
}
printf("%d\n",b);
return 0;
}

Lo ejecutamos con un valor grande del argumento:

linux> gcc -O3 fibo.c -o fiboc
linux> time ./fiboc 10000000
10

real 0m0.268s
user 0m0.240s
sys 0m0.004s

Ahora vamos a escribir algo parecido en Haskell aunque lógicamente de forma recursiva (aunque luego veremos algunas
alternativas curiosas):

import System(getArgs)

main = do
args <- getArgs
let n = read (args!!0)
print $ fib n 1 1

fib 2 _ b = b
fib n a b = fib (n-1) b (a|+|b)

a |+| b = mod (a+b) 13

El tiempo requerido es aproximadamente el doble que el de la versión en C anterior:

linux> ghc --make -O2 [Link] -o fiboh
[1 of 1] Compiling Main ( [Link], fibo.o )

5
 Linking fiboh ...
linux> time ./fiboh 2 10000000
10

real 0m0.564s
user 0m0.536s
sys 0m0.000s

Podemos afirmar que la pérdida de eficiencia no es excesiva, sobre todo si tenemos en cuenta que está trabajando con
Integer de tamaño ¡ilimitado! (muy poquito más lentos que el tipo Int de la máquina, lo cual me sorprende, debo
comprobarlo. . . )

De todas formas, podemos esperar que escribiendo el código sin ningún cuidado, el tiempo de cálculo aumente alrededor
de 10x en relación a C. Normalmente, esto se puede mejorar bastante, a veces sacrificando la claridad (lo cual no tiene
ningún sentido, en mi opinión). En la página shootout hay una comparativa de muchos lenguajes (de la que en realidad
no puede concluirse nada, ya que la gracia está precisamente en cambiar los pesos de lo que consideras importante en la
puntuación para que tu lenguaje favorito gane). Lo curioso es que teniendo en cuenta únicamente la velocidad de ejecución
Haskell no sale muy mal parado.

3 Ejemplos Sencillos

En esta sección mostramos algunos trocitos de código Haskell para hacernos una idea de cómo funciona. En esta página
hay una colección de ejemplos de programación sencillos y explicados: Haskell Wiki: 99 Haskell exercises.

3.1 Alternativas sintácticas

Nuestro primer ejemplo es la tı́pica función factorial, que tiene una implementación recursiva tı́pica, muy similar a la que
escribirı́amos en C:

fact n = if n==0
then 1
else n * fact (n-1)

La evaluación de la función consigue el resultado esperado:

Main> f 4
24

La aplicación de funciones se hace sin paréntesis, poniendo los argumentos a continuación y tiene la máxima precedencia
en las expresiones con operadores. Es interesante observar que el scope se consigue con la indentación (layout), de manera
intuitiva (o si se desea, explı́citamente con llaves y punto y coma).

También podemos definir la función dando diferentes definiciones para distintos (constructores de) datos:

fact 0 = 1
fact n = n * fact (n-1)

También podemos definirla ‘a trozos’:

fact n | n==0 = 1
| n<0 = error("fact de negativo")
| otherwise = n * fact (n-1)

donde hemos tratado de detectar un valor de entrada malo:

Main> f (-4)
*** Exception: fact de negativo

O mediante la construcción case:

6
 fact n = case n of
0 -> 1
n -> n * fact (n-1)

Esto también funciona, si no queremos usar la indentación:

fact n = case n of {0->1;n->n*fact(n-1)}

Y otra forma más serı́a usar la notación de listas de datos enumerables:

fact n = product [1..n]

Donde la notación anterior construye una lista, que incluso puede ser infinita:
Main> sum (take 5 [1..])
15

En realidad, sum y product son casos particulares del concepto fold: la ‘reducción’ de una lista mediante una cierta
operación binaria (que podemos pensar que sustituye a la coma que separa los elementos de la lista), y con un cierto valor
inicial (que podemos pensar que sustituye a la lista vacı́a del final). En el preludio hay varias versiones de fold. Por
ejemplo, podrı́amos escribir:

fact n = foldr (*) 1 [1..n]

En The evolution of Haskell programmer podemos encontrar muchas más formas de escribir la función factorial, con
comentarios humorı́sticos.

3.2 Operadores y list comprehensions

Ahora vamos a escribir una función que nos dice si un número es perfecto. Para ello definimos un operador para que luego
quede más claro el código, y los divisores de un número los expresamos como una list comprehension (crear una lista
sacando elementos de otra (u otras), y que cumplan ciertas condiciones):

infixl 5 <| -- Definimos un nuevo operador

n <| m = mod n m == 0 -- n es divisible por m

isPerfect n = sum (divis n) == n

where
divis n = [x | x <- [1..n-1], n <| x]
-- la lista de los x entre 1 y n-1
-- que dividen exactamente a n

Parece que funciona:

Main> take 3 (filter isPerfect [1..])
[6,28,496]

Con una list comprehension también podemos generar fácilmente tripletas pitagóricas:

triplets n = [(y,x,z)| z <- [2..], x<-[1..z], y <- [1..x-1], xˆn + yˆn == zˆn]

Si n = 2 encontramos infinitas soluciones. Para valores más grandes equivaldrı́a a refutar el último teorema de Fermat:
*Main> triplets 2
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17),(12,16,20),(15,20,25),
(7,24,25),(10,24,26),(20,21,29),(18,24,30),(16,30,34),Interrupted.
*Main> triplets 3
Interrupted.

7
En realidad una list comprehension no es más que syntactic sugar de una combinación del filter y map, por lo que
podrı́amos haber escrito también (es cuestión de gustos):

divis n = filter (n <|) [1..n-1]

En esta versión hemos ‘seccionado’ el operador <|, lo que no es más que la aplicación parcial de uno de los argumentos,
creando una función de un solo argumento. Por ejemplo:
Prelude> map (3*) [1..5]
[3,6,9,12,15]

Prelude> filter (>=7) [1..10]

[7,8,9,10]

Prelude> map ((3+).(ˆ2)) [1..7]

[4,7,12,19,28,39,52]

En el último caso hemos aplicado la función que resulta de componer la elevación al cuadrado y la suma de 3 sobre una
lista de números. Lo mismo puede hacerse definiendo sobre la marcha una función (el sı́mbolo \ significa λ):
Prelude> map (\x -> xˆ2+3) [1..7]
[4,7,12,19,28,39,52]

El signo menos (-) sirve para dos cosas: restar y cambiar el signo, por lo que a veces hay que poner un paréntesis en el
paso de argumentos: f 3 (-2). Sin paréntesis, f 3 -2 significa (f 3) - 2. Por esa razón, seccionar la resta por la
izquierda es mejor hacerlo con substract.
Prelude> map (2-) [1..5]
[1,0,-1,-2,-3]
Prelude> map (subtract 3) [1..5]
[-2,-1,0,1,2]

3.3 Recursión

Uno de los algoritmos tı́picos que Haskell permite implementar de manera muy elegante es quicksort:

qsort [] = []
qsort (x:xs) = qsort a ++ [x] ++ qsort b
where a = [ y | y <- xs , y < x ]
b = [ y | y <- xs , y >= x ]

O más directamente:

qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Parece que funciona bien:

Main> qsort [1,9,8,2,3,7]
[1,2,3,7,8,9]

Reconozco que solo cuando lo he visto escrito ası́ he comprendido bien el algoritmo.

Otra forma de ordenar es mezclar dos sublistas ordenadas:

mergeSort [] = []
mergeSort [a] = [a]
mergeSort xs = merge (mergeSort a) (mergeSort b)
where
(a,b) = splitAt (length xs ‘quot‘ 2) xs
merge [] b = b
merge a [] = a
merge (a:as) (b:bs)

8
 | a < b = a: merge as (b:bs)
| otherwise = b: merge (a:as) bs

También funciona:
Main> mergeSort [1,9,8,2,3,7]
[1,2,3,7,8,9]

En CodeCodex: Merge sort podemos comparar otros lenguajes (no sé si de forma absolutamente imparcial. . . ). La única
versión más corta es la de Python, pero porque al parecer la función merge está disponible de manera predefinida (!).

Otro ejemplo muy elegante de definición recursiva es la generación de permutaciones de una lista:

import [Link](delete)

permus [x] = [[x]]

permus xs = [x:ps | x <- xs, ps <- permus (delete x xs)]

Que, por supuesto, funciona con listas de cualquier tipo base:

Main> permus [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Main> unwords (permus "cosa")
"cosa coas csoa csao caos caso ocsa ocas osca osac oacs oasc scoa scao
soca soac saco saoc acos acso aocs aosc asco asoc"

Se puede mejorar la eficiencia con alguna función auxiliar, tal y como propuso el autor de esta implementación, Sebastian
Sylvan, aparecida en la lista Haskell-Cafe. (El problema es que delete quita el elemento buscando uno igual, no
quita lo que hay en una determinada posición de la lista, que en este caso serı́a bastante más eficiente si la lista contiene
elementos más complejos que un número). Además falları́a si hay elementos repetidos.

3.4 Correcursión

Haskell permite definiciones correcursivas, en las que las llamadas recursivas no tienen por qué aplicarse a un caso más
simple del problema. Si se hacen las cosas bien pueden funcionar porque la evaluación es no estricta.

Un ejemplo tı́pico de esto es una Criba de Eratóstenes sobre una lista de números infinita:

primos = sieve [2..]

where
sieve (p:ns) = p : sieve [x | x <- ns , x ‘mod‘ p /= 0]

Se va generando la lista solución en términos de elementos de ella misma, de manera ‘sana’, sin desparramar en consumo
de memoria.

El funcionamiento parece correcto:

Main> primos
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,12Interrupted.

Ejercicio: reescribe sieve usando map y filter.

Realmente tenemos los primos en una lista infinita, de manera que la primera vez que pedimos un elemento tarda un rato
en calcularlo, pero la segunda vez continúa calculando a partir de lo que ya tiene. Esto se llama memoization:
*Main> :set +s
*Main> primos!!1000
7927
(2.41 secs, 39956832 bytes)
*Main> primos!!1001
7933
(0.00 secs, 0 bytes)

9
 *Main> sum (take 1000 primos)
3682913
(0.00 secs, 0 bytes)

(Para que el intérprete ghci nos dé información de tiempo y espacio requerido por la computación usamos la opción
:set +s. Observa también que la versión compilada es más rápida.)

Como los elementos de la lista infinita de primos están ordenados, podemos comprobar fácilmente si un elemento está o
no en ella:

esPrimo n = n ‘elem‘ (fst $ span (<=n) primos)

(usamos la función ‘elem‘ de forma infija para facilitar la legibilidad). Funciona bien:
Main> esPrimo 1001
False

Observa que en ningún momento hemos puesto un lı́mite a los números con los que podemos trabajar.

En el siguiente ejemplo nos enfrentamos al caso tı́pico de una doble recursión que si se programa ingenuamente se vuelve
intratable:

fibo 0 = 1
fibo 1 = 1
fibo n = fibo (n-1) + fibo (n-2)

Ası́, por ejemplo:

Main> fibo 35
14930352
(8.93 secs, 1435761932 bytes)

Como alternativa podemos fabricar una lista infinita con los elementos de la sucesión, donde cada elemento se calcula a
partir de los anteriores (el operador !! extrae el elemento deseado de una lista, empezando por cero):

fibos = [Link][fibos!!(i-1) + fibos!!(i-2) | i <-[2 ..] ]

fibonacci = (fibos!!)

Esto ya es mucho más eficiente:

Main> fibonnaci 35
14930352
(0.01 secs, 0 bytes)

Otra posiblidad que no indexa explicitamente los elementos es usar zip, que toma dos listas y devuelve una lista de tuplas:

fibos = [Link][a+b | (a,b) <- zip fibos (tail fibos)]

Las tuplas son combinaciones de dos o más datos del tipo que deseemos. Se usan mucho para devolver más de un resultado
en las funciones. En el caso más usual de 2-tuplas, las funciones fst y snd nos permiten sacar el primero y el segundo
elemento de la tupla, aunque suele quedar más elegante desestructurarlas con pattern matching.

Ahora bien, si se va a operar inmediatamente con los elementos de la tupla, es mejor usar zipWith, que cambia la tupla
por la aplicación de una función cualquiera:

fibos = [Link] zipWith (+) fibos (tail fibos)

Y otra posibilidad más es usar list comprehensions paralelas:

{-# OPTIONS -fglasgow-exts #-}

fibos = [Link][ x+y | x<- fibos | y <- tail fibos]

10
Esta construcción no está en el estandard Haskell98, es una extensión del lenguaje, que igual que otras también muy útiles
se consigue con la opción -fglasgow-exts en la lı́nea de órdenes o indicándolo en la primera lı́nea del código fuente.

3.5 Polimorfismo

La siguiente función obtiene una estimación robusta de la localización de una masa de datos que no es unimodal:

-- el algoritmo de estimacio’n robusta de localizacio’n

-- inventado por Pedro E Lo’pez de Teruel

import [Link](sortBy,transpose,minimumBy)

on f g = \x y -> f (g x) (g y)

robustLocation :: Ord b => (a -> a -> b) -> [a] -> [(a,b)]

robustLocation dis xs = mins where
mins = map (minimumBy (compare ‘on‘ snd)) dst
dst = transpose ds
ds = map getdis xs
getdis p = sortBy (compare ‘on‘ snd) [(p, dis p y) | y<-xs]

Sirve para cualquier tipo de dato y cualquier función de distancia. Por ejemplo, podemos probarlo con simples números:

dist x y = abs (x-y)

dat = [1,2,3,11,12,13,14,15::Double]

main = print $ robustLocation dist dat

Conseguirı́amos algo como:

*Main> main
[(1.0,0.0),(1.0,1.0),(2.0,1.0),(12.0,2.0),(13.0,2.0),(11.0,8.0),(11.0,9.0),(11.0,10.0)]

A partir de ahı́ es inmediato elegir el elemento en la posición deseada, o analizar la estructura de distancias para elegirlo
automáticamente. Por ejemplo, de 13 a 11 se pasa de distancia 2 a distancia 8, el mayor incremento en la secuencia,
por lo que la estimación final podrı́a ser 13. En una sección posterior utilizaremos este estimador para la fabricación de
clasificadores. En ese caso los datos serán vectores y la función de distancia algo como dist x y = norm (x-y).

El siguiente algoritmo consigue estimaciones robustas de modelos para explicar un conjunto de datos. La idea se en-
tiende fácilmente observando el código (aunque por brevedad no se muestran algunas funciones auxiliares). Se incluyen
comentarios aclaratorios sobre los argumentos que aparecerı́an en la documentación html generada automaticamente.

-- | versio’n ba’sica, no adaptativa del algoritmo RANSAC

ransac :: ([a]->t) -- ˆ modelador
-> (t -> a -> Bool) -- ˆ criterio de inlier
-> Int -- ˆ nu’mero de objetos necesarios para estimar cada modelo
-> Int -- ˆ nu’mero de repeticiones
-> [a] -- ˆ datos de entrada, que incluyen outliers
-> (t,[a]) -- ˆ resultado, en forma de (modelo, inliers)
ransac estimator isInlier n t dat = (result, goodData) where
result = estimator goodData
goodData = inliers bestModel
bestModel = maximumBy (compare ‘on‘ ([Link])) models
models = take t (map estimator (samples n dat))
inliers model = filter (isInlier model) dat

(La versión adaptativa es un poco más larga y liosa, por lo que no la incluyo aquı́.)

Ahora podemos usar ransac para lo que deseemos, simplemente definiendo la función de estimación básica y lo que se
considera inlier. Por ejemplo, para estimar homografı́as escribimos algo parecido a:

11
 isInlierHomog t h (dst,src) = norm (vd - vde) < t
where vd = vector dst
vde = inHomog $ h <> homog (vector src)

estimateHomography corresp = -- appropriate definition

niceHomography umbral = ransac estimateHomography (isInlierTrans umbral) 4

y para estimar matrices fundamentales hacemos algo análogo:

isInlierFund t f (x’,x) = epipolarQuality f x’ x < t -- defined elsewhere

estimateFundamental corresp = -- appropriate definition

niceFundamental umbral = ransac estimateFundamental (isInlierFund umbral) 8

Por supuesto, habrı́a que usar ransac adaptativo y, si se desea, recalcular el modelo final con los inliers encontrados.
También hay que tener cuidado con la normalización, etc. Todos esos detalles no se incluyen aquı́.

3.6 Cast explı́cito

En Haskell no hay typecasting automático. Debemos transformar siempre los tipos explı́citamente:

mean list = sum list / fromIntegral (length list)

la función length devuelve un entero, que no puede operarse con la división:

Prelude> sum [1,2,3] / length [1,2,3]

<interactive>:1:0:
No instance for (Fractional Int)
arising from use of ‘/’ at <interactive>:1:0-27
Possible fix: add an instance declaration for (Fractional Int)
In the expression: (sum [1, 2, 3]) / (length [1, 2, 3])
In the definition of ‘it’:
it = (sum [1, 2, 3]) / (length [1, 2, 3])

observa que, a pesar de que la lista parece de enteros, el sistema deduce que lo que contiene es algún tipo Fractional 1
ya que hay una división, pero no puede hacer nada con el denominador, que es un int. La función fromIntegral está
sobrecargada y convierte cualquier cosa ‘entera’ en cualquier cosa ‘fraccional’.

Observa que las constantes numéricas son sı́mbolos polimórficos (¿sobrecargados?):

Prelude> :set + t
Prelude> :m + Complex
Prelude Complex> 2.3 + 5.4
7.7
it :: Double
Prelude Complex> 2.3 + (5.4::Float)
7.7
it :: Float
Prelude Complex> 2.3 + (5.4::(Complex Double))
7.7 :+ 0.0
it :: Complex Double
Prelude Complex> (2.3::Double) + (5.4::Float)

<interactive>:1:17:
Couldn’t match expected type ‘Double’ against inferred type ‘Float’
In the second argument of ‘(+)’, namely ‘(5.4 :: Float)’
1 Para no agobiar a usuario, y solo en el intérprete, a los números cuyo tipo queda ambiguo se les da un tipo por omisión. Para los de punto flotante se

asume Double y para los enteros Integer (con tamaño ilimitado).

12
 In the expression: (2.3 :: Double) + (5.4 :: Float)
In the definition of ‘it’: it = (2.3 :: Double) + (5.4 :: Float)

Normalmente, el uso en otro lugar hace que el tipo de un objeto polimórfico quede especificado y casi nunca hay que hacer
anotaciones explı́citas de tipos.

3.7 Estructuras de Datos

Además de los tipos de datos básicos (Integer, Bool, Double, etc. y los tipos estructurados (listas y tuplas entre
otros), el programador puede definir sus propios tipos de datos de forma muy sencilla, mediante lo que se conoce como
(algebraic datatypes), en los que cada tipo tiene uno o más ‘constructores’, y cada uno contiene cero o más datos de
cualquier otro tipo. Veamos algunos ejemplos.

El siguiente tipo puede representar vectores del espacio 3D. Es una especie de registro con 3 campos double:

data Vector3 = Vec Double Double Double

p:: Vector3
p = Vec 2.5 8 (-3.2)

Podemos aprovecharlo para la definición de un cuaternión:

data Quaternion = Quat Double Vector3

Alternativamente podemos usar una notación más parecida a la de los registros, donde se da un nombre a los campos, que
son funciones de acceso a ellos:

data Pixel = Pt { pixRow :: Int, pixCol :: Int}

p = Pt 3 5 -- simple definition
q = Pt { pixRow = 3, pixCol = 5} -- explicit definition
r = p {pixRow = pixCol q + 7 } -- record update

Los tipos de datos pueden tener sus componentes parametrizados:

data Tripleta a = Tripleta a a a -- parametric type

x = Tripleta False True True :: Tripleta Bool

x = Tripleta 2 3 57 :: Tripleta Int

-- z = Tripleta False 7 8 doesn’t typecheck

Puede haber varios parámetros distintos:

data Raro a b = Raro a [b]

x = Raro 8.7 [4,3,2,-5] :: Raro Double Int

En este caso coincide el nombre del tipo y el del constructor. Eso se hace muchas veces y no hay ningún problema, ya que
el contexto siempre indica si nos referimos a un tipo o a un valor.

Los tipos pueden tener varios constructores alternativos y ser recursivos:

-- un a’rbol binario con un cierto tipo de objeto en los nodos y en las hojas.
data Tree a = Hoja a | Nodo a (Tree a) (Tree a)

x :: Tree Bool
x = Hoja False

13
 y :: Tree Int
y = Nodo 6 (Hoja 5) (Nodo 8 (Hoja 1) (Hoja 2))

Los tipos predefinidos también se podrı́an definir ası́ (aunque por eficiencia, en los tipos numéricos se haga internamente
de manera más eficiente):

data Bool = False | True

data Int = ... -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 ...

-- [a] is syntactic sugar for something like

-- data List a = Nil | Cons a (List a)
-- data [] a = [] | a : ([] a)

Se puede definir constructores de datos binarios mediante operadores que empiezan por :. Por ejemplo:

data Complex a = a :+ a

El tipo Maybe, disponible en la biblioteca estándar, sirve para contener datos opcionales o que fueden fallar:

data Maybe a = Just a | Nothing

safedivision :: Int -> Int -> Maybe Int

safedivision _ 0 = Nothing
safedivision a b = Just (a ‘div‘ b)

Como veremos en el capı́tulo de monads, será muy sencillo combinar tipos Maybe para transferir automáticamente valores
‘válidos’ o Nothing en una cadena de operaciones que pueden fallar.

3.8 Abstracción y modularización

El siguiente ejemplo muestra varios conceptos muy importantes de Haskell. Se trata de un módulo que suministra el tipo
pila:

module Stack (Stack, empty, push, pop, top, isEmpty) where

data Stack a = Stk [a]

empty = Stk []
push x (Stk xs) = Stk (x:xs)
pop (Stk (x:xs)) = Stk xs
top (Stk (x:xs)) = x
isEmpty (Stk xs) = null xs

-- sacado del Haskell wiki, OOP vs type classes

-- newtype can be used instead of data

Podemos hacer varias observaciones:

– El ejemplo muestra la forma de definir un módulo. Se le da un nombre, una lista de sı́mbolos a exportar y a continuación
las definiciones que deseemos. Si no hay lista de exportación todos los sı́mbolos serán visibiles. Las signaturas se deducen
del código.

– Este ejemplo también ilustra la forma de crear tipos de datos abstractos. El módulo exporta el tipo Stack pero no su
constructor Stk, que solo es visible dentro del módulo, en su implementación. El usuario solo puede trabajar con las
funciones exportadas: push, pop, etc.

– La implementación es extraordinariamente concisa, y su corrección prácticamente salta a la vista. Se hace en base a

una lista, añadiendo y eliminando elementos por la cabeza, lo que es eficiente (otras estructuras de datos ([Link]. una deque)

14
necesitarı́an una implementación más cuidadosa).

– La pila definida es polimórfica. Funcionará con cualquier tipo base: números, listas, tuplas, árboles o incluso otras pilas
de pilas. A pesar de ello, podemos compilar el código y guardarlo en una biblioteca de manera que posteriormente pueda
usarse con toda tranquilidad y agilidad.

– Dado que estamos en un entorno funcional, hay que insistir en que las operaciones con la pila generan nuevas pilas, no
mutamos el estado de una pila. A pesar de esto, no se generan copias, sino que se van añadiendo y quitando elementos a
la lista interna, que será parcialmente ‘compartida’ por las diferentes pilas que vayan surgiendo. Por ejemplo, si queremos
usar una pila para invertir una lista, metiendo todas los elementos y luego sacándolos, podrı́amos hacerlo ası́:

invierte obj = result where

pila = foldr push empty obj
result = saca pila []
where saca p l | isEmpty p = l
| otherwise = saca (pop p) (top p:l)

Parece que funciona:

*Main> invierte [1..5]
[5,4,3,2,1]
*Main> invierte "Alberto"
"otreblA"

Es sorprendente el poder expresivo de un mecanismo de modularización y abstracción tan sencillo.

3.9 Closures

La aplicación parcial de funciones es un mecanismo sintáctico muy práctico, como podemos apreciar en la siguiente
situación.

Nuestro interface con la GSL nos proporciona una sencilla función de integración numérica, que vamos a usar con una
precisión predefinida y sin preocuparnos mucho del error obtenido.

import GSL

quad f a b = fst $ integrateQAGS 1E-9 100 f a b -- with typical parameters

La probamos con la función f (x) = x2 entre 0 y 1:

*Main> :t quad
quad :: (Double -> Double) -> Double -> Double -> Double
*Main> quad (ˆ2) 0 1
0.3333333333333333

Podemos calcular π mediante la siguiente integral:

Z 1
4
π= dx
0 1 + x2

definiendo la función sobre la marcha:

*Main> quad (\x -> 4/(1+xˆ2)) 0 1
3.141592653589793
*Main> pi
3.141592653589793

(Por supuesto también podrı́amos definir f x = 4/(1+xˆ2) y hacer quad f 0 1)

Lo interesante es que con la aplicación parcial podemos definir muy fácilmente una función de integración 2D, prácticamente
igual que una definición matemática:

15
 quad2 f a b g1 g2 = quad h a b
where h x = quad (f x) (g1 x) (g2 x)

Vamos a probarla integrando una función de dos variables que nos da el volumen de una esfera de radio r:

volSphere r = 8 * quad2 (\x y -> sqrt (r*r-x*x-y*y))

0 r (const 0) (\x->sqrt (r*r-x*x))

main = do
print $ volSphere 2.5
print $ 4/3*pi*2.5**3 -- para comparar

Funcionará como es debido porque compila bien (typechecks). Pero para tranquilizar al lector desconfiado podemos
ejecutar el programa:
*Main> main
65.44984694978736
65.44984694978736

Y ya que estamos en el intérprete preguntamos por el tipo que tiene:

*Main> :t quad2
quad2 :: (Double -> Double -> Double)
-> Double
-> Double
-> (Double -> Double)
-> (Double -> Double)
-> Double

LLama bastante la atención que podemos usar desde Haskell una función de C de manera mucho más cómoda que en el
mismo C. Podemos experimentar con ella en el intérprete, usar la aplicación parcial del integrando para expresar claramente
una integral doble, y, lo que es más importante, los parámetros adicionales de las funciones se suministran de manera
natural mediante aplicación parcial, en lugar de usar punteros void a los que se hace un cast dentro de la función.

Otro ejemplo tı́pico que ha surgido en varias aplicaciones de vision: el usuario pincha con el ratón y queremos el punto
caliente más cercano para hacer algo con él. La función esencial es algo como:

on f g = \x y -> f (g x) (g y)

closest [] p = p
closest hp p = minimumBy (compare ‘on‘ dist p) hp
where dist (Pixel a b) (Pixel x y) = (a-x)ˆ2+(b-y)ˆ2

Sin embargo, la aplicación parcial no solo es útil desde el punto de vista sintáctico, ahorrando el trabajo de escribir
funciones auxiliares con la estructura de argumentos requerida por la función que la usa. Es mucho más que eso, debido al
concepto de closure, que intentaremos explicar con un ejemplo. En todo caso, la wikipedia:closure lo explica muy bien.

Consideremos la siguiente función, que tiene dos argumentos, uno de los cuales podemos considerar como un parámetro,
y el otro como el argumento ‘real’:

fun a x = 3*z -- algo simple

where z = work a -- algo muy costoso

La función se calcula muy fácilmente a partir de z, que requiere una computación ‘muy costosa’ work que solo depende
de a. Por ejemplo, a podrı́a ser una base de datos y z el resultado de un cierto proceso de aprendizaje. Si vamos a usar
muchas veces fun a, con el mismo a, sobre diferentes x, no tiene sentido estar recalculando z en cada llamada. Por
ejemplo, si hacemos:
f = fun 5

a = map f [1..1000]

b = map (fun 7) [1..1000]

16
queremos que z se calcule dos veces, no 2000. Que este tipo de optimización se produzca de forma automática depende
un poco del compilador. Si queremos estar seguros, compilamos con -O y escribimos la función explı́citamente ası́:

fun’ a x = g
where g x = 3*z -- sencillo
z = work a -- costoso

Cada aplicación parcial fun 5, fun 7, etc., formará una closure con su propio z precalculado de forma automática. En
otros lenguajes habrı́a que separar artificialmente (a veces es interesante hacerlo, pero no siempre) la construcción de los
z y pasarlos como parámetro a la función principal.

Este concepto se usa extensivamente en una sección siguiente, donde las máquinas de aprendizaje fabrican clasificadores,
capturando internamente los ejemplos, funciones de kernel, sus parámetros, etc., de forma automática.

En C++ se puede conseguir algo parecido con objetos función. Se define de una clase con operador () cuyo constructor
la inicializa con los argumentos necesarios. Sin embargo es como matar moscas a cañonazos; se necesitan muchas defini-
ciones auxiliares y no es muy práctico generar funciones sobre la marcha. De hecho existen bibliotecas que tratan de dotar
a C++ de esta capacidad, y lo consiguen, pero con menos claridad y elegancia.

3.10 Evaluación no estricta (lazy)

De forma parecida a la evaluación ‘shortcut’ de expresiones booleanas en C o de los pipes de Unix, donde un programa
consume la salida de otro, en Haskell solo se evalúan las expresiones que son estrictamente necesarias para obtener el
resultado necesario (normalmente forzado por una operación de entrada salida). Esto tiene la desventaja de una cierta
pérdida de eficiencia, pero en muchı́simas aplicaciones compensa con creces al permitir una mayor claridad y modularidad
del código. Por ejemplo, permite separar la ‘generación’ de candidatos a resolver un problema de la ‘comprobación’ de las
soluciones, como se observa a continuación.

Hay un método muy sencillo y curioso para calcular la raı́z de un número N . A partir de una estimación a la mejoramos
con 12 (a + N/a) (creo que es el método de Newton-Raphston). Converge muy rápidamente. Veamos como podemos
programarlo:

En primer lugar escribimos la función que mejora una cierta aproximación:

apro n a = 0.5 * (a + n/a)

y la probamos a ver qué tal funciona:

*Main> :t apro
apro :: (Fractional a) => a -> a -> a
*Main> apro 5 2
2.25

Ahora construimos la lista infinita de aproximaciones (empezando por n/2, un valor inicial no especialmente peor que
otro):

rs n = iterate (apro n) (n/2)

Y comprobamos que funciona:

*Main> :t rs
rs :: (Fractional a) => a -> [a]
*Main> rs 5
[2.5,2.25,2.236111111111111,2.2360679779158037,
2.23606797749979,2.23606797749979 ˆC

Por supuesto tenemos que interrumpir el programa. Ahora vamos a escribir una función que dada una lista de elementos,
me devuelve el primero que se repite:

fixedPoint ([Link]xs) | a == b = a
| otherwise = fixedPoint (b:xs)

17
Vemos que funciona:
*Main> :t fixedPoint
fixedPoint :: (Eq t) => [t] -> t
*Main> fixedPoint [1,2,3,4,5,5]
5

Finalmente combinamos la generación con la comprobación de que hemos terminado:

raiz n = fixedPoint (rs n)

*Main> raiz 7
2.6457513110645907
*Main> sqrt 7
2.6457513110645907
*Main> sqrt 7 - raiz 7
0.0
*Main> sqrt 2 - raiz 2
2.220446049250313e-16

Esto se puede mejorar un poco. En primer lugar, fixedPoint usa una comparación de igualdad estricta, que no tiene
mucho sentido en números de coma flotante. Por otro, recibe una lista. Quizá serı́a mejor que recibiera una función y
obtuviera el punto fijo de ella con una función de comparación genérica:

fix comp f a = fp (iterate f a)

where fp ([Link]xs) | comp a b = a
| otherwise = fp (b:xs)

Vemos que el tipo de fix es una función que recibe la función de comparación, la que genera las aproximaciones y
devuelve una función, que a partir del valor inicial devuelve el punto fijo:
*Main> :t fix
fix :: (t -> t -> Bool) -> (t -> t) -> t -> t

Nuestra función raiz anterior es el punto fijo de las aproximaciones apro (dado n) que empiezan en un cierto valor:
*Main> fix (==) (apro 2) 1
1.414213562373095

Podemos escribirlo ası́:

raiz’ n = fix (==) (apro n) (n/2)

Y funciona:
*Main> raiz’ 2
1.414213562373095

Lo interesante es que ahora podemos cambiar fácilmente la función de comparación y la de generación de estimaciones.
Por ejemplo, vamos a comparar de manera que el valor absoluto sea menor que epsilon:

compabs e a b = abs (a-b) < e

Comprobamos que funciona bien:

*Main> fix (compabs 0.1) (apro 4) 1
2.05
*Main> take 10 (iterate (apro 4) 1)
[1.0,2.5,2.05,2.000609756097561,2.0000000929222947,2.000000000000002,2.0,2.0,2.0,2.0]

También podemos comparar por tamaño relativo (aunque en este ejemplo no se nota mucho la diferencia entre ambos por
el tamaño pŕoximo a la unidad de las aproximaciones):

comprel e a b = abs (a-b) / a < e

18
¿Funcionará con raı́ces cúbicas?
*Main> fix (comprel 1E-6) (\a->0.5*(a+27/aˆ2)) 1
3.000001383950946

Parece que sı́. Entonces vamos a intentar una raı́z n-sima:

root k n = fix (comprel 1E-6) (apro k n) 1

where apro k n a = 0.5*(a+n/aˆ(k-1))

Desafortunadamente, funciona solo a medias:

*Main> root 3 27
3.000001383950946
*Main> root 3 1000ˆ3
999.9984735702694
*Main> root 4 2ˆ4
Interrupted.

Con raı́ces grandes se pone a oscilar. . .

La evaluación no estricta nos permite también incluir en una estructura de datos elementos ‘derivados’ de los esenciales,
aunque se utilicen en pocas ocasiones. Solo se calculará en cada caso lo que sea realmente necesario. Un caso tı́pico es
la descripción estadı́stica de una población. Nos interesa la media, la matriz de covarianza, los vectores y valores propios,
etc. Una función, digamos stat, puede definir todo eso y luego extraemos lo que haga falta, sin repetir cálculos. Tampoco
tenemos que preocuparnos por generar todas las soluciones de un problema aunque a veces solo se necesite una.

Parece ser que el equational reasoning es mucho más potente en lenguajes con laziness.

4 Clases de Tipos

Una de las diferencias más grandes de Haskell con respecto a otros lenguajes es el concepto de ‘clase de tipos’. No se trata
de las clases de los lenguajes orientados a objetos. Aunque haya alguna relación (analizada en OOP vs type classes) se
trata de un concepto distinto; es mejor no intentar “traducir” los conceptos de un enfoque al otro, sino considerarlos como
complementarios.

En cierto sentido la programación consiste en definir funciones que convierten valores de unos tipos en otros. Sin embargo,
está claro que no resulta nada cómodo usar diferentes sı́mbolos para la suma de Int y la suma de Double, o diferentes
sı́mbolos para ordenar listas de Float y listas de Bool, etc. Necesitamos reutilizar o sobrecargar las funciones para
que trabajen con diferentes tipos de manera natural y consistente. Por ejemplo, en algunos lenguajes como C++ eso se
hace mediante herencia o mediante la definición de una función con el mismo nombre pero diferentes argumentos. Es un
mecanismo muy flexible y práctico en muchos casos.

En Haskell, la filosofı́a es ligeramente distinta. Consideremos todos los tipos de datos del lenguaje, ya sean ‘simples’,
estructurados, predefinidos o definidos por el usuario. Tenemos que imaginar que dentro de este universo de tipos hay
conjuntos (clases), en los que podemos meter los tipos que deseemos, sin exigir una estructura jerárquica. Por ejemplo,
la clase Eq contiene los tipos sobre cuyos valores podemos preguntar si son iguales, tienen definido un operador (==).
Muchos tipos están en la clase Show, que posee la función show, capaz de convertir los valores en Strings, serializándolos.
También está la clase Read, que posee la función read capaz de analizar sintácticamente Strings para obtener un valor de
ese tipo. Una clase muy importante es Num, la de los objetos que se pueden sumar, restar y multiplicar. Hay muchas clases
de tipos en la biblioteca estándar, podemos verlas en este esquema:

19
En general, las funciones son del tipo más general compatible con las operaciones utilizadas, lo que se refleja en su
signatura. Consideremos las signaturas de las siguientes funciones polimórficas:

concat :: [a] -> [a] -> [a]

sort :: (Ord a) => [a] -> [a]

La primera de ellas es completamente general. Dada dos listas de un cierto tipo cualquiera, sin ninguna restricción,
concat devuelve otra lista de ese mismo tipo. Pero la segunda tiene un requisito. Su signatura se leerı́a ası́: sort es
una función que toma una lista, cuyos elementos son de cualquier tipo que esté en la clase Ord (o sea, cuyos elementos se
puedan comparar) y devuelve una lista de ese mismo tipo. Eso significa que podemos ordenar listas de números (todos los
tipos numéricos pertenece a la clase Ord, pero, por ejemplo, no podemos ordenar funciones:
*Main [Link]> sort [5,4,7]
[4,5,7]
*Main [Link]> let funs = [sin, (+4), \x->2*x+2]
*Main [Link]> map ($7) funs
[0.6569865987187891,11.0,16.0]
*Main [Link]> sort funs

<interactive>:1:0:
No instance for (Ord (Double -> Double))
arising from use of ‘sort’ at <interactive>:1:0-8
Possible fix:
add an instance declaration for (Ord (Double -> Double))
In the expression: sort funs
In the definition of ‘it’: it = sort funs

La función print solo funciona con tipos de la clase Show, (“mostrables”):

*Main [Link]> :t print
print :: (Show a) => a -> IO ()

La siguiente función require que sus argumentos estén en dos clases:

f :: (Show a, Eq a) => a -> a -> IO ()

f x y = if x == y then print x else print "hola"

Si una clase está incluida en otra, la signatura solo exige la más concreta:
*Main [Link]> :t (\x -> print(x+1))
(\x -> print(x+1)) :: (Num a) => a -> IO ()

Ya que todos los tipos de la clase Num están dentro de la clase Show.

Cada vez que creamos un tipo de datos lo acostumbrado es instalarlo en unas cuantas clases de tipos razonables, casi
siempre Show, Read, Eq (lo cual puede hacerse automáticamente). Si el tipo admite algo como sumas y restas podemos
instalarlo en Ord, Num, Floating, etc. Todo depende de la aplicación.

Como ejemplo, vamos a definir un árbol binario:

20
 data Binarbol a = Hoja a
| Nodo (Binarbol a) a (Binarbol a)
deriving(Show,Read,Eq)

a = Nodo (Hoja 7) 5 (Nodo (Hoja 2) 13 (Hoja 1)) -- para hacer pruebas

La instrucción deriving hace que el compilador cree instancias razonables (basadas en los componentes) de las clases
indicadas. (Esto solo se puede hacer con las clases Eq, Ord, Enum, Bounded, Show, and Read, en las que no hay am-
biguedad, y nos permite empezar a trabajar cómodamente. Si lo deseamos luego podemos definirlas nosotros de otra
forma.) Comprobamos que las instancias funcionan:
*Main> show a
"Nodo (Hoja 7) 5 (Nodo (Hoja 2) 13 (Hoja 1))"

*Main> Nodo a 7 a
Nodo (Nodo (Hoja 7) 5 (Nodo (Hoja 2) 13 (Hoja 1))) 7 (Nodo (Hoja 7) 5 (Nodo (Hoja 2)
13 (Hoja 1)))

*Main> a /= a
False
*Main> a == Hoja 6
False

El intérprete hace print a la expresión evaluada, y para ello utiliza show. La función read funciona con cualquier tipo
base en el árbol:
*Main> read "Hoja False":: Binarbol Bool
Hoja False
*Main> read "Hoja [4,5,6]":: Binarbol [Int]
Hoja [4,5,6]

Para poder aplicar cómodamente una función a todos los elementos del árbol vamos a instalar nuestro tipo en la clase
Functor:

instance Functor Binarbol where

fmap f (Hoja x) = Hoja (f x)
fmap f (Nodo izq x der) = Nodo (fmap f izq) (f x) (fmap f der)

Ahora podemos hacer lo siguiente:

*Main> fmap (+5) a
Nodo (Hoja 12) 10 (Nodo (Hoja 7) 18 (Hoja 6))

*Main> fmap (filter odd) $ Nodo (Hoja [1,2,3]) [4,5] (Hoja [6,7,8])
Nodo (Hoja [1,3]) [5] (Hoja [7])

La función fmap es la versión general de map (para listas), que funciona en cualquier tipo functor. En realidad deberı́amos
usar fmap también para listas, pero por tradición se ha mantenido la versión map en el preludio:
*Main> :t fmap
fmap :: (Functor f) => (a -> b) -> f a -> f b
*Main> fmap even [1..5]
[False,True,False,True,False]

El tipo Maybe también es un functor:

*Main> fmap (*2) Nothing
Nothing
*Main> fmap (*2) (Just 5)
Just 10

Para ilustrar cómo se define una instancia numérica, vamos a definir operaciones aritméticas con árboles, elemento a
elemento, y si hay que operar una hoja con un nodo se utiliza el valor de la hoja en común para todo el subárbol que
le corresponde. Por claridad definimos antes la aplicación de un operador cualquiera sobre árboles con la interpretación
deseada:

21
 binop op (Hoja x) (Hoja y) = Hoja (x ‘op‘ y)
binop op (Nodo i x d) (Nodo i’ x’ d’) = Nodo (binop op i i’) (x ‘op‘ x’) (binop op d d’)
binop op h@(Hoja x) n@(Nodo _ _ _) = binop op (Nodo h x h) n
binop op n@(Nodo _ _ _) h@(Hoja _) = binop (flip op) h n

Con binop y fmap es inmediato definir las operaciones numéricas:

instance Num a => Num (Binarbol a) where

(+) = binop (+)
(-) = binop (-)
(*) = binop (*)
fromInteger = Hoja . fromInteger
signum = fmap signum
abs = fmap abs

Comprobamos que funcionan como deseamos:

*Main> a + (Nodo (Hoja 1) 2 (Hoja 3))
Nodo (Hoja 8) 7 (Nodo (Hoja 5) 16 (Hoja 4))

*Main> 5*a-7
Nodo (Hoja 28) 18 (Nodo (Hoja 3) 58 (Hoja (-2)))

*Main> aˆ2
Nodo (Hoja 49) 25 (Nodo (Hoja 4) 169 (Hoja 1))

*Main> a - a
Nodo (Hoja 0) 0 (Nodo (Hoja 0) 0 (Hoja 0))

Por supuesto, las operaciones numéricas no funcionan con árboles cuyos tipos no sean numéricos:
*Main> 3*Hoja False

<interactive>:1:0:
No instance for (Num Bool)
arising from the literal ‘3’ at <interactive>:1:0
Possible fix: add an instance declaration for (Num Bool)
In the first argument of ‘(*)’, namely ‘3’
In the expression: 3 * (Hoja False)
In the definition of ‘it’: it = 3 * (Hoja False)

También podemos definir nuestras propias clases de tipos, que tendrán operadores que podrán ser utilizados sobre todos
aquellos datos cuyos tipos se hayan hecho instancias de él. Como ejemplo, vamos a inventarnos una clase de tipos,
caracterizados porque admiten una operación rara:

class Rara a where

(ˆ|ˆ) :: a -> a -> a

Cuando se aplica a listas, la operación rara hace, por ejemplo, lo siguiente:

instance Rara [a] where

a ˆ|ˆ b = a ++ reverse b

*Main> [1..5] ˆ|ˆ [1..3]

[1,2,3,4,5,3,2,1]

Y cuando se aplica a árboles como los anteriores, la operación rara hace otra cosa (completamente distinta y también
absurda, pero con la misma signatura):

instance Num a => Rara (Binarbol a) where

a ˆ|ˆ b = Nodo a 0 (fmap (+5) b)

Observa que la operación rara sobre árboles exige que el tipo base sea numérico:

22
 *Main> Hoja 4 ˆ|ˆ Nodo (Hoja 3) 7 (Hoja 7)
Nodo (Hoja 4) 0 (Nodo (Hoja 8) 12 (Hoja 12))

Y no se admitirá con tipos base que no lo sean:

*Main> Hoja False ˆ|ˆ Hoja True

<interactive>:1:0:
No instance for (Num Bool)
arising from use of ‘ˆ|ˆ’ at <interactive>:1:0-23
Possible fix: add an instance declaration for (Num Bool)
In the expression: (Hoja False) ˆ|ˆ (Hoja True)
In the definition of ‘it’: it = (Hoja False) ˆ|ˆ (Hoja True)

Activando la extensión -fglasgow-exts es posible definir clases con varios parámetros, es decir, relaciones entre
tipos. Por ejemplo, una ‘colección’ puede tener como parámetros el contenedor y el tipo base. Otro ejemplo podrı́a ser un
producto matricial más o menos general, que admita matrices y vectores. La signatura de ese producto serı́a a -> b ->
c y la clase podrı́a ser Multip a b c, con instancias Multip Mat Mat Mat, Multip Mat Vec Vec, Multip
Vec Mat Vec, e incluso Multip Vec Vec Double. Las clases multiparamétricas se usan frecuentemente con ‘de-
pendencias funcionales’ para que el compilador pueda eliminar automáticamente posibles ambigüedades en expresiones
complicadas. P. ej., en el caso de la multiplicación matricial se definirı́a algo como Multip a b c | a -> b, in-
dicando que el tipo c queda determinado por los argumentos del producto. Usando esta técnica es posible sobrecargar
funciones teniendo en cuenta no solo el tipo de los argumentos sino también el del resultado.

La definición correcta de clases de tipos es uno de los aspectos más complejos de Haskell. Muchas veces, para conseguir
lo que uno desea es necesario utilizar extensiones del lenguaje que pueden abrir la caja de Pandora. . .

5 Entrada/Salida y otras Mónadas

La Monad es una clase de tipos distintiva de Haskell. No es fácil explicar lo que tienen en común, lo mejor es mostrar
varios ejemplos, que nos transmitirán algo de intuición. Posteriormente intentaremos formalizar este concepto. Mientras
tanto, se puede consultar este tutorial: All about monads.

5.1 IO Monad

Para dar una idea de cómo se maneja la entrada/salida, vamos a plantear una serie de ejercicios. La idea es que el lector
piense como resolverı́a el problema en su lenguaje favorito antes de ver la solución que se muestra aquı́.

- Escribe un programa que escriba en la salida estándar el máximo común divisor de los números que se pasan como
parámetros en la lı́nea de órdenes:

import System

mcd 0 0 = error "mcd 0 0 is undefined" -- or mcd 0 0 = undefined

mcd x y = gcd’ (abs x) (abs y)
where
gcd’ x 0 = x
gcd’ x y = gcd’ y (x ‘rem‘ y)

main = do
args <- getArgs
let nums = map read args
case nums of
[] -> error ("no has puesto argumentos")
_ -> print $ foldl mcd 0 nums

La función mcd es esencialmente una copia de gcd disponible en el preludio. Observa que getArgs :: IO [String]
y que read :: (Read a) => String -> a.

23
- Escribe un programa que escriba en la salida estandar el mı́nimo común múltiplo de los números que llegan por la entrada
estándar.

import System

mcd 0 0 = error "mcd 0 0 is undefined" -- or mcd 0 0 = undefined

mcd x y = gcd’ (abs x) (abs y)
where
gcd’ x 0 = x
gcd’ x y = gcd’ y (x ‘rem‘ y)

mcm n m = (n*m) ‘div‘ mcd n m

fun :: [Integer] -> Integer

fun [] = undefined
fun xs = foldl mcm 1 xs

main = do
cadena <- getContents
let datos = map read (words cadena)
print (fun datos)

- Escribe un programa que vaya escribiendo en stdout el mı́nimo común múltiplo de los números que van apareciendo en
lı́nea a lı́nea en stdin

(ejercicio para el lector)

El tipo IO a tiene como valores la descripción de acciones que, si se ejecutan, pueden realizar alguna operación de
entrada/salida y después entregan un valor de tipo a:
putStrLn "Hola" :: IO ()

getChar :: IO Char

print :: (Show a) => a -> IO ()

readFile :: FilePath -> IO String

Podemos guardar en una lista varias ’acciones’:

a = [putStrLn "Hola", print (2+2)] :: [IO()]

Y luego ejecutarlas, si nos parece oportuno:

Main > head a
Hola
Main > sequence a
Hola
4

Las acciones son un tipo de dato más, que se puede manipular de forma funcional, pura. Esto nos permite definir nuestras
propias estrategias de control. Por supuesto, llegará un momento en el que las acciones definidas se efectuarán, como
consecuencia de invocar a la función main, y, en ese momento, se empezarán a realizar realmente cálculos; hasta ese
momento todo han sido definiciones.

Es importante recordar que el mundo funcional y el mundo real están comunicados por una puerta que una vez que se
traspasa ya no hay vuelta atrás: toda función que usa entrada salida para obtener un tipo a tendrá una signatura acabada en
IO a, ([Link]. String -> IO Int), y ese ‘pecado’ no se le puede ‘perdonar’ jamás2 . Por ejemplo, si preguntamos al
compilador por el tipo de

addChar s = do
c <- getChar
return (c:s)
2 Hmm. . . , no deberı́a hablar de esto, pero existe unsafePerformIO, no recomendado para principiantes, y necesario para implementar llamadas

a funciones externas, si confiamos en que el código escrito es puro.

24
que añade un carácter tecleado por el usuario a la cadena que recibe como entrada, nos dirá:
*Main> :t addChar
addChar :: [Char] -> IO [Char]

Efectivamente, funciona (la primera x la teclea el usuario):

*Main> addChar "hola"
x"xhola"

Si ahora combinamos esa función con otras, la signatura empieza a contaminarse con el tipo IO:
*Main> :t map
map :: (a -> b) -> [a] -> [b]

*Main> :t map addChar

map addChar :: [[Char]] -> [IO [Char]]

Esto permite separar y aislar completamente la parte de procesamiento de datos ‘pura’ de nuestra aplicación, donde rigen
las leyes matemáticas de la transparencia referencial, y en las que el compilador puede aplicar transformaciones y opti-
mizaciones sin ningún peligro, de la parte ‘imperativa’, en la que es necesaria una secuenciación estricta de acciones.

Como se comenta humorı́sticamente en la retrospectiva citada en la introducción, Haskell no ha sucumbido a los cantos de
sirena de los efectos colaterales, manteniendo una actitud extremadamente puritana, como monjes en un monasterio. Esto
tiene inicialmente un coste muy elevado, y muchos lenguajes han caı́do en la tentación. Pero es una actitud que al final
compensa: los pactos con el diablo (los efectos colaterales) terminan pasando factura, y vienen a cobrarse la deuda cuando
menos te lo esperas. Por el contrario, un lenguaje puro supone un esfuerzo mayor, por el que se paga al principio, pero que
merece la pena al final.

Los tipos IO a están en la clase Monad, que tienen la notación do y <-, para enfatizar su significado imperativo, pero
que en realidad se pueden manipular con el operador de “secuenciación” >>=
*Main> :t (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

y con la función return, que mete su argumento en la mónada correspondiente:

Prelude> :t return
return :: (Monad m) => a -> m a

En el caso IO:
(>>=) :: IO a -> (a -> IO b) -> IO b
return :: a -> IO a

Por ejemplo:
getLine :: IO String

readFile :: FilePath -> IO String

getLine >>= readFile :: IO String

writeFile :: FilePath -> String -> IO ()

getLine >>= readFile >>= (writeFile "filename" . reverse) :: IO ()

La última función es equivalente a:

do name1 <- getLine

cadena <- readFile name1
let rev = reverse cadena
writeFile "filename" rev
return ()

El operador >>= es análogo a la composición de funciones, pero haciendo entrada salida cada vez (y leı́do en ‘dirección

25
contraria’). Si las acciones no tienen resultado (o no lo usamos) se pueden combinar con el operador >>.

Otro ejemplo más interesante de secuenciación con >>= puede verse en el siguiente trozos de código, que usa un interfaz
experimental a las funciones de procesamiento de imagen de la IPP, a las que accedemos como operaciones de entrada
salida (aunque muchas de ellas en realidad podrı́an tratarse como funciones puras).

-- | Returns a list of interest points in the image (as unnormalized [x,y]).

-- | They are the local minimum of the determinant of the hessian (saddlepoints).
getCorners :: Int -- ˆ degree of smoothing (e.g. 1)
-> Int -- ˆ radius of the localmin filter (e.g. 7)
-> Float -- ˆ fraction of the maximum response allowed (e.g. 0.1)
-> Int -- ˆ maximum number of interest points
-> ImageFloat -- ˆ source image
-> IO [Pixel] -- ˆ result
getCorners smooth rad prop maxn im = do
let suaviza = smooth ‘times‘ gauss Mask5x5
h <- suaviza im >>= secondOrder >>= hessian >>= scale32f (-1.0)
(mn,mx) <- minmax h
hotPoints <- localMax rad h
>>= thresholdVal32f (mx*prop) 0.0 IppCmpLess
>>= getPoints32f maxn
return hotPoints

Finalmente, planteamos otro ejercicio en el que se utiliza entrada y salida:

- Define un tipo de datos que sea un árbol recursivo, cuyas hojas son de un cierto tipo, donde cada nodo contiene otro
posible tipo de datos, y de él cuelga un número arbitrario de subárboles. Dado un número que se pasa como argumento
crea un árbol de la estructura de divisores, guárdalo en dı́sco, leelo de disco, y escribe en la salida estándar la suma de
todas las hojas.

import System

data Tree h n = Hoja h

| Nodo n [Tree h n]
deriving (Show,Read)

divis n = [x | x <- [2..n-1], n ‘rem ‘ x == 0]

crea n = case divis n of

[] -> Hoja n
ds -> Nodo n (map crea ds)

sumah (Hoja h) = h
sumah (Nodo _ as) = sum (map sumah as)

main = do
args <- getArgs
let n = read (args!!0)
let arbol = crea n
writeFile "[Link]" (show arbol)
cadena <- readFile "[Link]"
let tree = read cadena :: Tree Int Int
print (sumah tree)

5.2 Monad Parser

Las instancias de las funciones show y read que se crean automáticamente pueden no ser muy bonitas:
> crea 12
Nodo 12 [Hoja 2,Hoja 3,Nodo 4 [Hoja 2],Nodo 6 [Hoja 2,Hoja 3]]

26
ası́ que:

- Escribe un analizador sintáctico que lea árboles como el anterior con una gramática más sencillita, por ejemplo algo como
(12 :-> 2 3 (4 :-> 2) (6 :-> 2 3)), y crea un árbol de, por ejemplo, nodos Bool y hojas Float a partir de
(True :-> (2 3 (False :-> 7) 5).

La siguiente solución usa un monadic parser de la biblioteca estándar. Si nos fijamos, se utiliza la notación do, <-, etc.,
pero ahora no significa entrada y salida y secuenciación de acciones, sino ‘extraer’ cosas que van cumpliendo la gramática,
que se define de forma composicional:

{-# OPTIONS -fno-monomorphism-restriction #-} -- je je

import System
import [Link]

data Tree h n = Hoja h

| Nodo n [Tree h n]
deriving (Show,Read,Eq)

analiza cadena = case parse parser "" cadena of

Right arbol -> arbol
Left e -> error (show e)

parser = pnodo <|> phoja

phoja = do
h <- word
return $ Hoja (read h)

pnodo = do
char ’(’
spaces
node <- word
spaces
string ":->"
spaces
hojas <- sepEndBy1 (parser) spaces
spaces
char ’)’
return $ Nodo (read node) hojas

word = many1 alphaNum -- muy mal

main = do
print (analiza "45" :: Tree Int Int)
print (analiza "(True :-> 2 23( False:->4 7 9 )5)" :: Tree Integer Bool)

Al ejecutarlo con las cadenas de prueba de la función main funciona como esperamos:
*Main> main
Hoja 45
Nodo True [Hoja 2,Hoja 23,Nodo False [Hoja 4,Hoja 7,Hoja 9],Hoja 5]

Pero es solo un esbozo muy preliminar, para dar una idea de lo que se puede hacer. (Para hacerlo bien, genérico de verdad,
etc., habrı́a que definir tokens adecuadamente, etc.)

5.3 List Monad

Ahora vamos a mostrar otra situación en la que aparece la notación do, <-, etc., que tampoco es para entrada y salida.
Antes de nada, observa el siguiente ejemplo:

cosa = do

27
 p <- [1 .. 5]
q <- [2,4,6]
return (p+q)

obtendrı́amos
Main> cosa
[3,5,7,4,6,8,5,7,9,6,8,10,7,9,11]

Cuando se trata de listas, esa sintaxis trata de capturar la idea de computaciones no deterministas, que pueden obtener
varias soluciones y por tanto en los cálculos se generan todas las combinaciones (está muy relacionado con las list com-
prehensions. En cualquier caso, el siguiente ejercicio serı́a:

- Resuelve el problema de las n-queen como caso particular de un algoritmo de búsqueda exhaustiva y backtracking.

Este ejercicio ilustra las operaciones de la clase de tipos mónada, en su instancia para listas. Intentaremos escribir de forma
concisa un algoritmo general de búsqueda exhaustiva (¿en profundidad?):

import [Link](guard, mplus)

Lo siguiente es una función de búsqueda general. Recibe una lista de estados válidos (podrı́amos pensar en tableros de un
juego), una función okfun que nos dice si un estado es final (o sea, que es bueno y no hay que buscar más) y una función
sucfun que genera una lista de sucesores posibles a partir de un estado. El funcionamiento es muy sencillo: si el primer
elemento de la lista de casos pendientes es bueno lo añadimos al resultado como tal y seguimos buscando en los demás. Si
no, seguimos buscando en sus sucesores y los sucesores de los demás.

genSearch :: (a -> Bool) -> (a -> [a]) -> [a] -> [a]
genSearch _ _ [] = []
genSearch okfun sucfun (b:bs) = do
let search = genSearch okfun sucfun -- para abreviar un poco
if okfun b
then b: search bs
else search (sucfun b ‘mplus‘ bs ) -- mplus de listas es (++)

Ya está, lo podrı́amos guardar compilado en un módulo aparte.

Ahora vamos a utilizar esto en un problema concreto: encontrar todas las soluciones al problema de las n reinas. Definamos
una estructura de datos que representa el tablero. Podrı́amos hacerlo ası́:

data Board = Board Int [Int] [Int] [Int]

pero preferimos una definción más autoexplicativa, en forma de registro. Además, instalamos este tipo de datos en la clase
de los tipos que se pueden mostrar, definiendo adecuadamente la función show (sobrecargada) de forma que muestre en
modo texto las piezas en el tablero:

data Board = Board { size :: Int

, cols :: [Int]
, diags :: [Int]
, idiags:: [Int]
}

instance Show(Board) where

show (Board _ cs _ _) = concat $ map ((flip pos) (length cs)) cs
where spaces = repeat ’ ’
pos k n = take (k-1) spaces ++ ’O’ : take (n-k) spaces ++ "|\n"

Para poder usar la función de búsqueda general sólo nos falta definir cuándo una solucion es buena:

okqueen desiredSize board = desiredSize == size board

y generar los sucesores válidos de una posición:

28
 queenFollowers size (Board ar cs ds fs) = do
let r = ar+1
c <- [1..size]
guard (not (elem c cs))
guard (not (elem (c-r) ds))
guard (not (elem (r+c) fs))
return $ Board r (c:cs) ((c-r):ds) ((r+c):fs)

queen n = genSearch (okqueen n) (queenFollowers n) [Board 0 [] [] [] ]

main = do mapM_ print $ queen 8

mapM_ print $ queen 4

*Main> head (queen 25)

O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O|
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |
O |

5.4 State Monad

Otra situación en la que la abstracción monádica es útil es en la encapsulación de estado. Supongamos que queremos
programar la sucesión de Fibonacci cambiando progresivamente los dos últimos términos calculados hasta el momento:

import [Link]

update :: State (Int,Int) Int

update = do
(s,sa) <- get
let n = s + sa
put (n,s)
return n

fibo k = fst $ execState (replicateM k update) (1,0)

Esta mónada tiene las funciones propias get y put para extraer y modificar el estado, que en este ejemplo no es más
que una pareja de enteros. La función return genera un resultado ‘observable’ en las transiciones (en este ejemplo no es
particularmente útil). Observa el funcionamiento:
*Main> runState update (2,1)

29
 (3,(3,2))

*Main> runState (replicateM 10 update) (1,0)

([1,2,3,5,8,13,21,34,55,89],(89,55))

*Main> fibo 10
89

Expresamos un algoritmo iterativo de manera funcional, pura. Podriamos pensar en la implementación de un filtro de
Kalman usando esta técnica. . .

5.5 Maybe Monad

El tipo Maybe comentado anteriormente también está dentro de la clase de las mónadas. En este caso sus operaciones
sirven para encadenar funciones que pueden ‘fallar’:

foo x | odd x = Nothing -- only works with even numbers

| otherwise = Just (2*x+1)

bar x | x ‘rem‘ 3 /= 0 = Nothing -- only works with multiples of three

| otherwise = Just (3*x-2)

*Main> foo 4
Just 9
*Main> foo 5
Nothing

*Main> bar 3
Just 7
*Main> bar 4
Nothing

*Main> Just 2 >>= foo

Just 5

*Main> Just 2 >>= foo >>= bar

Nothing

*Main> Just 4 >>= foo >>= bar

Just 25

Se puede hace exactamente lo mismo con la notación do:

f x = do
a <- foo x
b <- bar a
return b

Por ejemplo:
f :: (Integral a) => a -> Maybe a
*Main> f 2
Nothing
*Main> f 4
Just 25

Es importante darse cuenta de que la f definida tiene el mismo tipo que foo y bar, se podrı́a combinar con ellos de la
misma forma, con >>= o la notación do:
*Main> Just 7 >>= foo >>= f >>= bar
Nothing

30
6 Utilidades

6.1 QuickCheck

Esta biblioteca es muy práctica para depurar. Dada una propiedad de tu algoritmo (una función booleana que debe ser
cierta para todas las entradas), esta biblioteca la comprueba automáticamente con un conjunto de entradas ‘arbitrarias’ de
‘tamaño’ creciente. Y lo hace sin que el usuario tenga que escribir prácticamente nada de código adicional.

Por ejemplo, está claro que aplicar dos veces reverse debe obtener el resultado inicial:
Prelude> :m + [Link]
Prelude [Link]> :t quickCheck
quickCheck :: (Testable a) => a -> IO ()
Prelude [Link]> quickCheck (\a -> reverse (reverse a) == a)
Loading package QuickCheck-1.0 ... linking ... done.
OK, passed 100 tests.
Prelude [Link]>

Veamos si es cierto que

a 1
= b
b a

No lo es por varias razones:

Prelude [Link]> quickCheck (\a b -> a/b == 1/(b/a))
Falsifiable, after 8 tests:
0.0
0.0
Prelude [Link]> quickCheck (\a b -> a/b == 1/(b/a))
Falsifiable, after 0 tests:
3.3333333333333335
-2.3333333333333335

Esta herramienta es capaz de descubrir un montón de bugs originados por no considerar como listas vacı́as, divisiones por
cero, etc.

Vamos a ver un ejemplo más realista de lo útil que es quickCheck. Volvemos a escribir la función de ordenación y una
propiedad que debe cumplir, que cada elemento sea menor o igual que el siguiente:

import [Link]

qsort [] = []
qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>x) xs)

prop1 l = and $ zipWith (<=) s (tail s)

-- [a <= b | a <- s | b <- tail s]
where s = qsort l

*Main> quickCheck prop1

OK, passed 100 tests.

Si queremos podemos ver las pruebas que hace:

*Main> verboseCheck prop1
0:
[]
1:
[3]
2:
[]
3:
[]
4:

31
 []
5:
[3,-3,-2]
6:
[4,2,3,-5,4]
7:
[-4,3,-1,-3]
8:
[-4,2,0,-1]
etc.

Hay que tener en cuenta que si en lugar de trabajar en el intérprete (donde los tipos numéricos tienen un default) las
metemos en el código tenemos que indicar el tipo base concreto:

main = do
quickCheck (prop1 :: [Double]->Bool)
verboseCheck (prop1 :: [Int]->Bool)

Parece entonces que el quicksort está bien programado. Pero para quedarnos más tranquilos vamos a comprobar alguna
propiedad más. Por ejemplo, que todos los elementos de la lista están en la lista ordenada:

xs ‘containedIn‘ ys = all (‘elem‘ ys) xs

prop2 l = l ‘containedIn‘ (qsort l) && (qsort l) ‘containedIn‘ l

*Main> quickCheck prop2

OK, passed 100 tests.

También es correcto. Bueno, aunque sea un poco pesado, para estar completamente seguros, vamos a comprobar que la
lista original y la ordenada tienen la misma longitud:

prop3 l = length l == length (qsort l)

Lo probamos y nos damos cuenta de que ¡hay un bug!

*Main> quickCheck prop3
Falsifiable, after 5 tests:
[3,3]

En la segunda llamada recursiva habı́amos copiado mal y puesto qsort (filter (>x) xs) en lugar de qsort
(filter (>=x) xs) y por tanto si habı́a elementos duplicados solo se metı́a uno en la lista ordenada.

La idea es escribir las propidades de tus funciones importantes, incluso antes que su implementación, y pasar una baterı́a
de tests justo antes de cada commit en el repositorio (se puede automatizar).

(pendiente un ejemplo más ilustrativo, donde creamos la instancia arbitrary de nuestros tipos de datos).

6.2 OpenGL

Está disponible en las biblioteca estándard: HOpenGL.

6.3 GUI

Hay dos bastante buenos: Gtk2Hs y wxhaskell.

6.4 Estructuras de datos funcionales

Hay varias en la biblioteca estándar, y también en Edison.

32
6.5 Profiling

El compilador integra una herramienta para poder estudiar los cuellos de botella de los programas. Por ejemplo, consider-
emos el siguiente ejemplo sencillo:

f x = x ‘quot‘ 2
g x = 3*x+1

collatz :: Integer -> Integer

collatz x | even x = f x
| otherwise = g x

col n = fst $ span (>1) $ iterate collatz n

lon n = length (col n)

main = print $ maximum (map lon [1..100000])

Lo compilamos con soporte para profiling y lo ejecutamos indicando al sistema de tiempo real de Haskell que deseamos el
informe de ejecución:
linux>ghc --make -O [Link] -prof -auto-all
[1 of 1] Compiling Main ( [Link], collatz.o )
Linking collatz ...
linux> ./collatz +RTS -p
178

Durante la ejecución se crea el informe [Link], que contiene lo siguiente:

linux> cat [Link]

Sat Dec 9 14:40 2006 Time and Allocation Profiling Report (Final)

collatz +RTS -p -RTS

total time = 3.85 secs (77 ticks @ 50 ms)

total alloc = 1,387,709,120 bytes (excludes profiling overheads)

COST CENTRE MODULE %time %alloc

col Main 54.5 87.1

collatz Main 24.7 6.2
f Main 10.4 4.1
g Main 7.8 2.1
main Main 1.3 0.4
lon Main 1.3 0.1

individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc

MAIN MAIN 1 0 0.0 0.0 100.0 100.0

main Main 160 1 0.0 0.0 0.0 0.0
CAF Main 154 1 0.0 0.0 100.0 100.0
main Main 161 0 1.3 0.4 100.0 100.0
lon Main 162 100000 1.3 0.1 98.7 99.6
col Main 163 100000 54.5 87.1 97.4 99.5
collatz Main 164 10753840 24.7 6.2 42.9 12.4
g Main 166 3564892 7.8 2.1 7.8 2.1
f Main 165 7188948 10.4 4.1 10.4 4.1
CAF [Link] 107 3 0.0 0.0 0.0 0.0

Observamos la estructura de llamadas y el tiempo consumido por las distintas funciones, tanto por sı́ mismas (individual),
como incluyendo el tiempo de las funciones auxiliares invocadas (inherited).

Hay muchas opciones de profiling, que pueden consultarse en el manual del compilador.

6.6 Cabal

Instalación y distribución de bibliotecas: muy fácil.

6.7 Haddock

Es un sistema que fabrica documentación html a partir de los comentarios del código, análogo a Doxygen de C++.

33
6.8 Darcs

Es un sistema de control de revisiones escrito en Haskell, basado en una teorı́a matemática de los parches. Está bastante
bien porque puedes hacer commit offline y mandar parches por email al dueño del respositorio sin necesidad de tener
privilegios en su máquina.

6.9 Concurrencia

Haskell nos permite lanzar concurrentemente varias acciones (funciones de tipo IO a) de forma muy sencilla. En el
siguiente programita un proceso escribe una larga cadena de aes en el terminal, a la vez que otro escribe una larga cadena
de bs.

main = do
let n = 100000
forkIO $ do
putStrLn (replicate n ’a’)
putStrLn $ (replicate n ’b’)

Las aes y bs aparecen entremezcladas:

*Main> main
aaabbbaaaaaabbbbaaa
... etc...
aaaaaa

La biblioteca de concurrencia proporciona varias abstracciones de comunicación. Por ejemplo, las MVar son ‘variables’
con semáforo, en las que solo puedes escribir si están vacı́as o leer si están llenas (en caso contrario el proceso se queda
esperando). También hay canales de comunicación, etc.

(ejemplo más completo)

Recientemente se está trabajando con una nueva abstracción más potente para la concurrencia: Software Transactional
Memory (STM).

En Tackling the akward squad se explican los aspectos más relacionados con el mundo real: Entrada/Salida, concurrencia,
llamadas a funciones de otros lenguajes, etc.

Las versiones de ghc recientes tienen soporte SMP y por tanto pueden conseguir verdadero paralelismo: Haskell Wiki:
concurrency.

6.10 Tipos existenciales

Supongamos que queremos hacer una lista heterogénea, de objetos de varios tipos. Es importante estar estáticamente
seguro de que en tiempo de ejecución no se mete un tipo en la lista que luego, al sacarlo, se le aplique una función que no
es admisible.

6.11 Programación genérica

– Ejercicio: dada cualquier estructura de datos definida por el usuario, escribe una función que busque en ella todos los
componentes de un cierto tipo y les aplique una función. Por ejemplo, que incremente todos los enteros que hay en una
estructura, posiblemente recursiva.

Esto es posible hacerlo en Haskell de forma muy sencilla:

import [Link]

f :: Int -> Int

34
 f = (+1)
genincr = everywhere (mkT f)

La función genincr admite todo tipo de datos, e incrementa los enteros que encuentra:
*Main> :t genincr
genincr :: forall a. (Data a) => a -> a

*Main> genincr "hola"

"hola"
*Main> genincr [1,2,3::Double]
[1.0,2.0,3.0]
*Main> genincr [1,2,3::Int]
[2,3,4]
*Main> genincr ("hola",length "hola")
("hola",5)

Funciona con cualquier tipo de datos. Debe estar en la clase Typeable y Data, pero las instancias las crea automáticamente
el compilador:

data KK = KK {a :: Int, b :: Double} deriving (Typeable,Data,Show)

x = KK 2 3
y = [KK 1 2, KK 3 4]

*Main> genincr x
KK {a = 3, b = 3.0}
*Main> genincr y
[KK {a = 2, b = 2.0},KK {a = 4, b = 4.0}]
*Main> genincr (y,(x,y))
([KK {a = 2, b = 2.0},KK {a = 4, b = 4.0}],(KK {a = 3, b = 3.0},
[KK {a = 2, b = 2.0},KK {a = 4, b = 4.0}]))

Más información en Haskell Wiki: Generic Programming.

7 Ejemplo: Pattern Recognition

Una aplicación interesante en la que la programación funcional ha resultado muy cómoda es en la definición de los algo-
ritmos sencillos de reconocimiento de patrones. El código completo está dentro de la distribución de GSLHaskell, por si
se quiere mirar la implementación detallada. Aquı́ solo comentaremos las ideas principales.

Nuestro objetivo es diseñar ‘aprendedores’, que analizan un conjunto de vectores etiquetados y devuelven una función de
clasificación.

type Example = (Attributes,Label)

type Classifier = Attributes -> Label

type Sample = [Example]

type Learner = Sample -> Classifier

Nos gustarı́a evaluar la calidad de cada máquina entrenándola con unos ejemplos y obteniendo su tasa de error y su matriz
de confusión.

errorRate :: Sample -> Classifier -> Double

confusion :: Sample -> Classifier -> Matrix Double

Ahora bien, el Classifier ¿sólo admite como argumento el objeto a clasificar? Normalmente será una función que tiene
parámetros, optimizados en el aprendizaje. Ası́ que las funciones de evaluación anteriores deberı́an usar el clasificador con

35
la estructura generada por su algoritmo de ajuste. Y lo mismo pasa con el Learner, que deberá recibir parámetros de
trabajo ([Link]. tipo de kernel y sus parámetros en una svm, capas y nodos en una red neuronal, etc.) Este es, al menos,
el enfoque al que estamos acostumbrados. El diseño de esto en C++ nos obliga a pensar muy bien lo que queremos,
y posiblemente tendremos que adivinar el futuro. Vamos a ir paso a paso viendo lo que conseguimos con aplicación
parcial y closures, lo que nos permite hacer ‘combinadores’ de funciones que se construyen unas a partir de otras como si
fueran datos. El objetivo es tener una especie de ‘mecano’ de máquinas de clasificación cuyas piezas se puedan combinar
libremente y sobre la marcha.

La primera observación es que un clasificador nos va a entregar dos cosas, el clasificador en sı́, que dado un vector de
atributos de entrada nos devuelve la clase predicha, y un estimador, que devuelve una lista de la ‘verosimilitud’, distancia, o
fuerza de cada clase. El clasificador puede construirse a partir del estimador, tomando la clase más problable. Esto significa
que solo tenemos que preocuparnos de construir estimadores. Cuando lo tengamos, podemos construir un clasificador:

createClassifier :: InfoLabels -> Estimator -> Classifier

createClassifier ilbs f = getLabel ilbs . posMax . f

No vamos a entrar en los detalles del tipo InfoLabels, simplemente contiene información sobre las etiquetas encontradas
en la muestra, y funciones para convertir eficientemente códigos en etiquetas y viceversa.

Un ‘estimador’ de clases muy sencillo está basado en una función de distancia. Por ejemplo la distancia a la media:

type Distance = [Attributes] -> Attributes -> Double

ordinary :: Distance
ordinary vs = f where
m = -- la media de los datos vs
f x = norm (x-m)

Hemos creado un tipo especial anticipando que nos gustarı́a trabajar con otras posibles funciones de distancia.

Con ella podemos fabricar un clasificador general:

-- | A generic distance-based learning machine.

distance :: Distance -> Learner
distance d exs = (c,f) where
(gs,lbs) = group exs
distfuns = map d gs
f x = map (negate.($x)) distfuns
c = createClassifier lbs f

Es muy importante resaltar que esta función calcula las funciones de distancia a todos los conjuntos de vectores de cada
clase y se las guarda internamente (en su closure) sin tener que preocuparnos de ellas. Y por supuesto, cada máquina de
clasificación creada con (c,f) = distance dist prob, para diferentes problemas y funciones de distancia, tendrá
internamente sus datos internos independientes.

Veamos cómo funciona:

Main> study problem (distance ordinary)

La función study (que no merece la pena detallar aquı́) coge el problema (una lista de vectores con sus clases), lo divide
en dos trozos (master y test), entrena el clasificador, muestra la tasa de error y la matriz de confusión sobre la muestra de
test y si el problema es de 2 atributos dibuja con gnuplot un bonito mapa de clasificación.

(mostrar el resultado de ejecutar esto)

Ahora podemos inventar nuevas funciones de distancia:

-- | Mahalanobis’s distance to a population.

mahalanobis :: Distance
mahalanobis vs = f where
m = -- mean of vs
ic = inverse of covariance matrix of vs
f x = (x-m) <> ic <> (x-m)

36
 -- | distance to the nearest neighbour
nn :: Distance
nn vs v = minimum (map (dist v) vs)
where dist x y = norm (x-y)

Y podemos probarlas exactamente igual:

Main> study problem (distance mahalanobis)

(mostrar varios)

Algunas funciones de distancia pueden tener parámetros, eso no nos preocupa:

-- | distance to the pca subspace of each class

subspace :: PCARequest -> Distance
subspace rq vs = f where
Codec {encodeVector = e, decodeVector = d} = pca rq (stat (fromRows vs))
f v = norm (v - (d.e) v)

Se usarı́a ası́ (en estos problemas 2D de juguete no tiene mucho sentido, pero con los caracteres manuscrito de la base
mnist funciona bastante bien):

*Main> study problem $ distance (subspace (NewDimension 2))

*Main> study problem $ distance (subspace (ReconstructionQuality 0.8))

La función study o distance pueden estar precompiladas desde hace años y admiten perfectamente nuevas (gener-
adores de) funciones de distancia que se nos ocurran. La aplicación parcial de sus posibles parámetros de funcionamiento
las deja en forma del tipo Distance requerido.

Por supuesto, hay métodos más avanzados para fabricar clasificadores, por ejemplo una ¡red neuronal! Es muy sencilla de
programar. La red se representa simplemente como una lista de matrices de pesos.

-- given a network and an input we obtain the activations of all nodes

forward :: NeuralNet -> Vector Double -> [Vector Double]
forward n v = scanl f (join [v,1]) (weights n)
where f v m = tanh (m <> v)

-- given a network, activations and desired output it computes the gradient

deltas :: NeuralNet -> [Vector Double] -> Vector Double -> [Matrix Double]
deltas n xs o = zipWith outer (tail ds) (init xs) where
dl = (last xs - o) * gp (last xs)
ds = scanr f dl (zip xs (weights n))
f (x,m) d = gp x * (trans m <> d)
gp = gmap $ \x -> (1+x)*(1-x)

updateNetwork alpha n (v,o) = n {weights = zipWith (+) (weights n) corr}

where xs = forward n v
ds = deltas n xs o
corr = map (scale (-alpha)) ds

epoch alpha n prob = foldl (updateNetwork alpha) n prob

backprop alpha n prob = scanl (epoch alpha) n (repeat prob)

Esto es lo esencial. Simplemente necesitamos alguna función auxiliar para pasar las etiquetas a códigos posicionales, para
inicializar la red, etc. Lo importante es que tenemos un estimador y (a partir de él) un clasificador. Y parece que funciona:
*Main> study problem (neural 0.1 0.05 100 [10])
*Main> study problem (neural 0.05 0.05 100 [20,10,5])

(mostrar)

37
Hasta ahora, hemos fabricando clasificadores multiclase completos (a partir del estimador). Pero lo cierto es que muchas
veces se desarrollan técnicas clasificación binaria que luego se extienden de forma más o menos sencilla al caso general.
Usamos la notación siguiente:

-- | A function that tries to discriminate between two classes of objects

type Feature = Attributes -> Double -- +/-

type TwoGroups = ([Attributes],[Attributes]) -- +/-

-- | A learning machine for binary classification problems.

type Dicotomizer = TwoGroups -> Feature

Es muy sencillo crear el ‘combinador’ multiclass. Lo que hace es crear un conjunto de problemas en los que se trata de
distinguir una clase de todas las demás, se entrenan con el dicotomizador deseado, y las features obtenidas se juntan en un
estimador (y con él se obtiene el clasificador).

multiclass :: Dicotomizer -> Learner

multiclass bin exs = (createClassifier lbs f, f) where
(gs,lbs) = group exs
f = multiclass’ bin gs

multiclass’ bin [g1,g2] = (\x -> [x,-x]) . bin (g1,g2)

multiclass’ bin l = f where
fs = map bin (auxgroup l)
f v = map ($v) fs

auxgroup x = zip x (map (concat . flip delete x) x)

Para probarlo, necesitamos algún dicotomizador. Por ejemplo, una solución de mı́nimos cuadrados ingenua basada en la
pseudoinversa:

-- | mse linear discriminant using the pseudoinverse

mse :: Dicotomizer
mse (g1,g2) = f where
m = (fromRows g1 <-> fromRows g2) <|> constant 1 (size b)
b = join [constant 1 (length g1), constant (-1) (length g2)]
w = pinv m <> b
f v = tanh (join [v,1] <> w)

Funciona como debe (no muy bien en problemas no linealmente separables):

*Main> study problem (multiclass mse)

Para mejorarlo, podrı́amos intentar el kernel trick:

type Kernel = (Vector Double -> Vector Double -> Double)

delta f l1 l2 = matrix $ partit (length l1) $ [f x y | x <- l1, y <- l2]

kernelMSE :: Kernel -> Dicotomizer

kernelMSE kernel (g1,g2) = fun where
fun z = expan z ‘dot‘ a
expan z = vector $ map (kernel z) objs
a = pinv (delta kernel objs objs) <> labels
objs = g1 ++ g2
labels = join [constant 1 (length g1), constant (-1) (length g2)]

-- | polynomial ’Kernel’ of order n

polyK :: Int -> Kernel
polyK n x y = (x ‘dot‘ y + 1)ˆn

-- | gaussian ’Kernel’ of with width sigma

gaussK :: Double -> Kernel
gaussK s x y = exp (-(norm (x-y) / s)ˆ2)

38
Que funciona mucho mejor, encontrando una frontera no lineal (si usamos el kernel y su parámetro adecuado).
*Main> study problem (multiclass (kernelMSE (polyK 2)))
*Main> study problem (multiclass (kernelMSE (polyK 5)))
*Main> study problem (multiclass (kernelMSE (gaussK 0.2)))

Aunque por supuesto lo ideal serı́a enganchar con una buena implementación de las máquinas de vectores de soporte
propiamente dichas.

Esta infraestructura (que viene dada de forma natural en el lenguaje, ya que no hemos hecho nada raro para conseguirla)
nos permite escribir ‘metaclasificadores’ de forma inmediata. Se nos ocurren dos, en principio. Uno es los árboles de
clasificación y el otro el adaboost. Ambos tratarán de combinar dicotomizadores (tı́picamente débiles), para conseguir un
dicotomizador más fuerte (que luego se puede convertir en clasificador multiclase). Sin embargo, adaboost trabaja con
dicotomizadores que admiten un peso en cada ejemplo. A estos los llamamos WeightedDicotomizer.

type Weights = Vector Double

-- | An improved ’Dicotomizer’ which admits a distribution on the given examples.
type WeightedDicotomizer = TwoGroups -> Weights -> Feature

Uno tı́pico es stumps, que encuentra la mejor frontera perpendicular a un eje.

-- | weak learner which finds a good threshold on a single attribute

stumps :: WeightedDicotomizer

Serı́a bueno que todos los dicotomizadores fueran ponderados. Como no lo son, creamos dos combinadores que nos
permiten pasar de un tipo al otro mediante remuestreo de ruleta o pesos uniformes:

-- | Converts a ’WeightedDicotomizer’ into an ordinary ’Dicotomizer’ (using an uniform distribut

unweight :: WeightedDicotomizer -> Dicotomizer
unweight dic (g1,g2) = dic (g1,g2) w where
m = length g1 + length g2
w = constant (1/fromIntegral m) m

-- | Converts a ’Dicotomizer’ into a ’WeightedDicotomizer’ (by resampling).

weight :: Int -- ˆ seed of the random sequence
-> Dicotomizer -> WeightedDicotomizer
weight seed dic (g1,g2) w = dic (g1’,g2’) where
s = ungroup [g1,g2]
ac = scanl1 (+) (toList w)
rs = take (length ac) $ randomRs (0, 1::Double) (mkStdGen seed)
rul = zip ac s
elm pos = snd $ head $ fst $ partition ((>pos).fst) rul
[g1’,g2’] = fst (group (breakTies seed 0.0001 $ map elm rs))

En cualquier caso, definimos el algoritmo de construcción de un árbol de decisión:

-- | Creates a decision tree

treeOf :: (TwoGroups -> Bool) -> Dicotomizer -> Dicotomizer

treeOf stopQ method gs@(g1,g2) = if stopQ gs || not improved then leaf else node where
n1 = length g1
n2 = length g2
leaf = if n1>n2 then const 1 else const (-1)
node v = if d v > 0 then d1 v else d2 v
d = method gs
(g11,g12) = partition ((>0).d) g1
(g21,g22) = partition ((>0).d) g2
d1 = treeOf stopQ method (g11,g21)
d2 = treeOf stopQ method (g12,g22)
improved = (length g11, length g21) /= (n1,n2) &&
(length g12, length g22) /= (n1,n2)

39
 -- | stopping criterium for ’treeOf’. A new decision node is created if the minoritary class has
branch :: Int -> (TwoGroups -> Bool)
branch n (g1,g2) = min (length g1) (length g2) <= n

Que se usarı́a ası́:

study problem (multiclass $ treeOf (branch 0) mse)
let problem = (breakTies 0 0.1 $ rings 1000)
*Main> study problem (multiclass $ treeOf (branch 0) (unweight stumps))
*Main> study problem (multiclass $ treeOf (branch 0) (kernelMSE (polyK 2)))
*Main> study problem (multiclass $ treeOf (branch 0) (perceptron 0.1 0.1 10 [2]))

(perceptron es la versión Dicotomizador de la máquina neuronal comentada anteriormente.)

La implementación de adaboost no es complicada pero por brevedad solo mostramos la signatura. El primer argumento es
el número de rondas.

adaboost:: Int -> WeightedDicotomizer -> Dicotomizer

Y es muy fácil de usar:

let problem = (breakTies 0 0.1 $ rings 1000)
*Main> study problem (multiclass $ adaboost 100 stumps)
*Main> seed <- randomIO :: IO Int
1210918827
*Main> study problem (multiclass $ adaboost 100 (weight seed mse))

Y para terminar, llegamos a la “orgı́a composicional”:

let machine = multiclass $
adaboost 10 $
weight seed $ treeOf (branch 5) $
perceptron 0.1 0.1 10 [2]
*Main> study problem machine

Es decir, hacer un clasificador multiclase a partir de de clasificadores binarios de tipo adaboost que combinan como
clasificador débil árboles de decisión cuyos nodos son redes neuronales de una capa oculta con 2 elementos. Como
adaboost required un dicotomizador ponderado se lo fabricamos sobre la marcha con la función weight. Podemos
imaginar cosas peores. . .

Todo esto se puede estudiar en el intérprete, aunque el código principal esté compilado.

Falta ver ejemplos con mnist, usando los combinadores de preprocesamiento (witPCA, etc.)
withPCA rq = withPreprocess (mef rq)
withMDF = withPreprocess mdf
study mnist (withPCA (NewDimension 20) $ distance ordinary)
study mnist (withPCA (ReconstructionQuality 0.9) $ withMDF $ distance mahalanobis’)

Finalmente, para ilustrar la reusabilidad de código vamos a escribir un clasificador por distancia a la localización robusta
obtenida por el algoritmo de PedroE, explicado en el capı́tulo 3. Solo tenemos que hacer algo como:

pedrodist prop l = f where

dist x y = norm (x-y)
f = dist m
m = fst (ds!!k)
ds = robustLocation dist l
k = round (prop*fromIntegral(length l)) -- no es lo ideal

y entonces podemos trabajar con máquinas como por ejemplo:

study problem (distance (pedrodist 0.8))

(falta mostrar resultado)

40
8 Ejemplo: Más correcursión

Este artı́culo de J. Karczamarczuk es fantástico: The Most Unreliable Technique in the World to compute π.

Se puede hacer algo parecido pero solo con sumas parciales de una serie muy sencillita, no con la suma completa como en
el artı́culo anterior, que aprovecha una expansión en la que sabemos que los dı́gitos ya no cambiarán.

Una fracción se representa mediante una base y la lista de sus infinitos dı́gitos:

data Frac = Frac Int [Int]

También podemos definirla al estilo de un record, que es más cómodo para poder sacar de ella ambos componentes y para
añadir campos en el futuro sin romper el código ya disponible.

data Frac = Frac { base:: Int,

digs:: [Int] }

La función frac n d calcula la expansión de n/d.

frac base 0 _ = Frac base (repeat 0)

frac base n d = Frac base (digits base n d)

digits base n d = a : digits base (base*b) d

where (a,b) = quotRem n d

-- metemos al tipo Frac en la clase Show haciendo que

-- muestre [Link]. los primeros 20 decimales
instance Show(Frac) where
show (Frac b (e:d)) = show e ++ "," ++ (concatMap show (take 20 d)) ++ "..."

Parece que se generan bien los dı́gitos:

*Main> frac 10 1 2
0,50000000000000000000...
*Main> frac 10 1 3
0,33333333333333333333...
*Main> frac 10 6 7
0,85714285714285714285...
*Main> frac 2 1 3
0,01010101010101010101...

Ahora vamos a implementar las operaciones aritméticas.

-- suma
Frac b u <+> Frac b’ v
| b == b’ = Frac b $ cpr b (zipWith (+) u v)
| otherwise = error "bases diferentes"

-- acarreos mirando al futuro

cpr b (u0:u1:us)
| u1 < b’ = u0 : cpr b (u1:us) -- seguro que no hay acarreo
| u1 > b’ = (u0+1) : cpr b (u1-b:us) -- seguro que hay
| u1 == b’ = let v1:vs = cpr b (u1:us) -- lo hay si lo hay en el siguiente...
in if v1 < b
then u0:v1:vs -- no lo ha habido
else u0+1:v1-b:vs -- lo ha habido
where b’ = b-1

-- para negar un decimal hacemos complemento a la base,

-- quedando positivos, y la parte entera se hace negativa.
neg (Frac b (u:us)) = Frac b $ (negate u -1) : map ((b-1) -) us

41
 a <-> b = a <+> neg b

-- aunque falla con fracciones acabadas en infinitos ceros,

-- ya que al sumar genera acarreo infinito. Se puede arreglar
-- pero no merece la pena arreglarlo para este ejercicio.

Parece que suma y resta bien:

*Main> frac 10 3 7 <-> frac 10 2 7
0,14285714285714285714...
*Main> frac 10 1 7
0,14285714285714285714...

(El tipo Frac se podrı́a instalar en la clase Num para poder usar +, *, etc.)

Ya podemos obtener sumas parciales de la fórmula de Leibniz:

∞
X (−1)n 1 1 1 1 1 π
=1− + − + − + ... =
n=0
2n + 1 3 5 7 9 11 4

Para alternar automáticamente los términos positivos y negativos podemos expresarlo también como:

∞
X 4 4
π= −
n=0
4n + 1 4n + 3

Parece que funciona:

*Main> let s = scanl1 (<+>) [frac 10 4 (4*k+1) <-> frac 10 4 (4*k+3) | k<-[0..]]

*Main> s!!400
3,14034577128141221542...

Pero converge de forma extraordinariamente lenta y, lo que es peor, no sabemos cuándo los dı́gitos son definitivamente
correctos:
*Main> s!!1000
3,14109315312144916643...

Por tanto lo mejor es utilizar la técnica propuesta en el divertido artı́culo de Karczamarczuk.

9 Cooperación con otros lenguajes

Se usa el fantástico Foreign Function Interface (FFI).

9.1 Haskell Main

9.1.1 C desde Haskell

Es muy sencillo usar funciones de C en Haskell, sobre todo si sus argumentos son solo tipos básicos o arrays de tipos
básicos. (Si son structs es un poco más difı́cil, pero se puede hacer y hay herramientas que pueden automatizar la tarea.
Como último recurso se pueden escribir funciones de acceso a los campos. . . )

Veamos un ejemplo muy simple. Supongamos que tenemos una función escrita en C:

42
 #include <stdlib.h>

double foo(int n, double r) {

double s = 1;
int k;
for(k=1; k<=n; k++) {
s*=r;
}
return s;
}

Y su correspondiente fichero de cabecera:

double foo(int n, double r);

La compilación de fun.c produce fun.o (también podrı́amos crear una biblioteca estática o dinámica).
gcc -c fun.c

Para usar esa función desde Haskell solo tenemos que usar la directiva de importación foreign:

{-# OPTIONS -fffi #-}

import Foreign

foreign import ccall "fun.h foo" foo :: Int -> Double -> Double

main = do
putStr "C call foo(7.5,3) = "
print (foo 3 7.5)

Y en la compilación añadir el código objeto (o la opción de enlace con una biblioteca):

ghc --make [Link] fun.o

El programa funciona como deseamos:

$ ./Main
C call foo(7.5,3) = 421.875

En realidad podrı́amos hacerlo directamente, ya que ghc trabaja con gcc:

ghc --make [Link] fun.c

Pero es más frecuente la forma anterior, para acceder a funciones de bibliotecas (estáticas o dinámicas) ya compiladas,
disponibles en el sistema.

Curiosamente, desde el intérprete podemos probar cómodamente la funcion C:

$ ghci Main fun.o
___ ___ _
/ _ \ /\ /\/ __(_)
/ /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98.
/ /_\\/ __ / /___| | [Link]
\____/\/ /_/\____/|_| Type :? for help.

Loading package base ... linking ... done.

Loading object (static) fun.o ... done
final link ... done
[1 of 1] Compiling Main ( [Link], interpreted )
Ok, modules loaded: Main.
*Main> foo 2 2
4.0

43
 *Main> foo 5 0.99
0.9509900498999999
*Main> foo 16 2
65536.0
*Main> foo 3 5
125.0
*Main> main
C call foo(7.5,3) = 421.875

9.1.2 C++ desde Haskell

También podemos usar en Haskell funciones de C++. Para ello solo debemos definirlas como extern "C" y enlazar
con libstdc++. Por ejemplo, la siguiente función de C++ usa una deque de la STL:

#include <cstdlib>
#include <deque>

extern "C" int foo(int n);

int foo(int n) {
std::deque<int> l;
for (int i = 1; i<=n; i++) {
l.push_back(i);
}
int s = 0;
for (int i = 0; i<[Link](); i++) {
s+=l[i];
}
return s;
}

Este es el fichero de cabecera:

int foo(int n);

Compilamos la función C++:

$ g++ [Link] -c

y ya tenemos fun.o.

Ahora escribimos el programa Haskell que usará la función C++:

{-# OPTIONS -fffi #-}

import Foreign

foreign import ccall "fun.h foo" foo :: Int -> Int

main = do
putStr "many calls to C++ foo = "
print (map foo [1..1000])

La compilamos añadiendo la biblioteca de C++:

$ ghc [Link] fun.o -L/usr/lib/gcc/i486-linux-gnu/4.0.3 -lstdc++

Y el programa parece funcionar:

$ ./[Link]

44
 many calls to C++ foo = [1,3,6,10,15,21,28,36,45,55,66,78,91,
...
,495510,496506,497503,498501,499500,500500]

Supongo que funcionará bien en casos más complejos, aunque no lo he probado. En algún sitio dice que la función main
la debe compilar g++, para inicializar cosas static, lo cual tiene sentido. Veremos lo que pasa en las aplicaciones serias que
llamen a C++.

Por otra parte, no he sido capaz de dar con la forma de usar la función anterior de forma interpretada, hay un sı́mbolo que
no logra encontrar en el enlace.

9.2 C o C++ Main

En este caso el procedimiento es similar para C y para C++, los ejemplos siguientes se refieren a C.

9.2.1 Ejemplo mı́nimo

El siguiente ejemplo muestra cómo podemos usar funciones escritas en Haskell desde nuestros programas en C.

Este es el código Haskell de una cierta función:

{-# OPTIONS -fffi #-}

module Fun where

foreign export ccall "hfun" f :: Int -> Int

f n | even n = n ‘quot‘ 2
| odd n = 3*n+1

Lo compilamos con:
ghc --make -Wall -O -c [Link]

Obtenemos un par de avisos sin importancia (en este caso):

[Link]:0: Warning: Definition but no type signature for ‘f’
[Link]:0:
Warning: Pattern match(es) are non-exhaustive
In the definition of ‘f’: Patterns not matched: _

La opción Wall nos dice de que la función definida no tiene signatura y que no está definida exhaustivamente. Deberı́amos
sustituir even n por otherwise. Para hacer la prueba esto no importa.

En cualquier caso, ha generado un código C auxiliar (fun stub.h y fun stub.c) y obtiene dos archivos objeto:
fun.o y fun stub.o. Ahora escribimos el programa en C donde la vamos a utilizar:

#include <stdio.h>
#include <stdlib.h>
#include "fun_stub.h"

int main(int argc, char *argv[])

{
hs_init(&argc, &argv);

printf("hfun(5) = %d\n", hfun(5));

hs_exit();
return 0;
}

45
Y lo compilamos con ghc (que se ocupa de llamar a gcc y a enlazar con todo lo necesario):
ghc -Wall -O pru.c fun.o fun_stub.o

El programa funciona como está previsto:

$ ./[Link]
hfun(5) = 16

9.2.2 Crear el ejecutable final con gcc

En casos más realistas nos interesará crear el ejecutable con gcc u otro compilador. No hay ningún problema, aunque la
lı́nea de órdenes es un poco más complicada. Mejor hacemos un Makefile:
HDIR=/home/brutus/apps/ghc-6.6/lib/i386-unknown-linux

HLIBS=-L$(HDIR) -lHShaskell98 -lHSbase -lHSbase_cbits -lHSrts -lm -lgmp -ldl -lrt \

-u base_GHCziBase_Izh_static_info -u base_GHCziBase_Czh_static_info \
-u base_GHCziFloat_Fzh_static_info -u base_GHCziFloat_Dzh_static_info -u base_GHCziPtr_Ptr_stat

HASKELL= -I$(HDIR)/include $(HLIBS)

fun.o: [Link]
ghc -O --make -Wall -c [Link]

pru: pru.c fun.o

gcc -O -Wall pru.c fun.o fun_stub.o $(HASKELL)

clean:
rm -f *.o *.hi *.out *_stub.c *_stub.h

Las bibliotecas que hay que enlazar se pueden averiguar mirando la salida de la compilación con ghc anterior añadiendo
la opción -v.

9.2.3 Transferencia de Arrays

Además de las funciones Haskell que operan con tipos básicos, puede ser muy útil usar desde C funciones que trabajan
con listas. Vamos a preparar un módulo que puede ser útil en el futuro:

46
 {-# OPTIONS -fffi #-}

module ArrayFun(mkC, mkC2, TLL) where

import Foreign

type TLL a b = Ptr a -> Int -> Ptr b -> Int -> Ptr Int -> IO Int

mkC :: Storable a => ([a]->[a]) -> (Ptr a -> Int -> IO Int)
mkC f p n = do
l <- peekArray n p
pokeArray p (f l)
return 0

mkC2 :: (Storable a, Storable b) => ([a]->[b]) -> TLL a b

mkC2 f pIn nIn pOut maxOut pNOut = do
l <- peekArray nIn pIn
let r = f l
let n = length r
if n <= maxOut
then do
pokeArray pOut r
poke pNOut n
return 0
else do
return 1

La función mkC convierte una función que crea una lista a partir de otra del mismo tipo en una función de C que recibe un
array (puntero y tamaño) y lo modifica con esa función. Por su parte mkC2 es parecida a la anterior, pero pone el destino
en un array distinto (indicando su tamaño real, que puede no ser el máximo del buffer), en este caso a partir de una función
[a]->[b] (cuyos tipos base pueden ser distintos).

Este módulo nos sirve como ayuda para exportar las funciones primo (que memoriza los primos que ha ido calculando)
y reverse (que convierte en double e invierte el orden de un array), que podemos definir ası́:

{-# OPTIONS -fffi #-}

module KK where

import ArrayFun

foreign export ccall "prime" prime :: Int -> Int

foreign export ccall "reverse" c_reverse :: TLL Int Double

c_reverse = mkC2 $ map fromIntegral . reverse

prime = (primes!!) where

primes = sieve [2..]
sieve (p:ns) = p : sieve [x | x <- ns , x ‘mod‘ p /= 0]

Ahora las usamos en un programa en C que podrı́a ser el siguiente. Observa que se imprimen los 10000 primeros numeros
primos, en orden directo e inverso, y luego se hace reverse a un array.

47
 #include <stdio.h>
#include <stdlib.h>
#include "funs_stub.h"

int main(int argc, char *argv[])

{
hs_init(&argc, &argv);

int i;
for(i=0; i<10000; i++) {
printf("%d ", prime(i));
}
for(i=10000; i>=0; i--) {
printf("%d ", prime(i));
} // estos áestn precalculados...
printf("\n");

int a[10] = {1,2,3,4,5,6,7,8,9,10};

double b[20];
int n;
int err = reverse(a,10,b,20,&n);
if(err) {
printf("Error en reverse\n");
exit(1);
}
for(i=0; i<n; i++) {
printf("%f\n",b[i]);
}

hs_exit();
return 0;
}

La parte relevante del Makefile que nos permite crear el programa serı́a algo ası́ como:
funs.o: [Link]
ghc -O --make -Wall -c [Link]

prus: prus.c funs.o

gcc -O -Wall prus.c ArrayFun.o funs.o funs_stub.o $(HASKELL)

Si ejecutamos el programa obtendremos algo como:

$ ./[Link]
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109
113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233
...
443 439 433 431 421 419 409 401 397 389 383 379 373 367 359 353 349 347 337 331 317 313
311 307 293 283 281 277 271 269 263 257 251 241 239 233 229 227 223 211 199 197 193 191
181 179 173 167 163 157 151 149 139 137 131 127 113 109 107 103 101 97 89 83 79 73 71 67
61 59 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2
10.000000
9.000000
8.000000
7.000000
6.000000
5.000000
4.000000
3.000000
2.000000
1.000000

La lista de primos inversa tarda mucho menos tiempo. Es un buen ejemplo de memoization.

48