• Author / Uploaded
• Javier Yo

Citation preview

R AZONANDO CON H ASKELL U N CURSO SOBRE ´ F UNCIONAL P ROGRAMACI ON

A Charo, Pepa, Ana y Chari

INTERNATIONAL THOMSON EDITORES SPAIN PARANINFO

hola

´ Blas Carlos Ruiz Jimenez, ´ ´ Francisco Gutierrez Lopez y Jose´ Enrique Gallardo Ruiz Profesores del Departamento de Lenguajes y Ciencias de la Computaci´on

Pablo Guerrero Garc´ıa Profesor del Departamento de Matem´atica Aplicada

E.T.S.I. Inform´atica. Universidad de M´alaga

R AZONANDO CON H ASKELL U N CURSO SOBRE ´ F UNCIONAL P ROGRAMACI ON

M´alaga, enero de 2004

c Blas C. Ruiz, Francisco Gutierrez, ´ ° Pablo Guerrero y Jose´ E. Gallardo c ITES-Paraninfo ° Edita: Imprime: ISBN: ... Dep´osito Legal: ... Composici´on: Realizada por los autores en LATEX2².

´INDICE GENERAL

´ Indice de figuras

XIII

Pr´ologo

XVII

Convenios

I

XXIII

Programaci´on funcional b´asica con H ASKELL 98

1. Programaci´on funcional 1.1. Funciones . . . . . . . . . . . . . . . . . . . . . 1.2. Sesiones y declaraciones . . . . . . . . . . . . . . 1.3. Reducci´on de expresiones . . . . . . . . . . . . . ´ 1.3.1. Ordenes de reducci´on aplicativo y normal 1.3.2. Evaluaci´on perezosa . . . . . . . . . . . 1.4. Sobre H ASKELL . . . . . . . . . . . . . . . . . . 2. Introducci´on a H ASKELL 2.1. El lenguaje H ASKELL . . . . . . . . . . 2.2. Tipos simples predefinidos . . . . . . . 2.2.1. El tipo Bool . . . . . . . . . . 2.2.2. El tipo Int . . . . . . . . . . . 2.2.3. El tipo Integer . . . . . . . . . 2.2.4. El tipo Float . . . . . . . . . . 2.2.5. El tipo Double . . . . . . . . . 2.2.6. El tipo Char . . . . . . . . . . 2.2.7. Operadores de igualdad y orden 2.3. Constructores de tipos predefinidos . . . 2.3.1. Tuplas . . . . . . . . . . . . . 2.3.2. Listas . . . . . . . . . . . . . . 2.3.3. El constructor de tipo (→) . . . 2.4. Comentarios . . . . . . . . . . . . . . . 2.5. Operadores . . . . . . . . . . . . . . . . 2.5.1. Operadores frente a funciones . 2.6. Comparaci´on de patrones . . . . . . . . 2.6.1. Patrones constantes . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

1 . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

3 3 4 6 9 9 11

. . . . . . . . . . . . . . . . . .

13 13 15 15 16 16 17 18 18 19 20 20 21 22 24 24 27 28 29

´Indice general

VI

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

32 33 34 35 36 36 37 38 38 39 40 41 42 43 45 46

3. Funciones de orden superior y polimorfismo 3.1. Parcializaci´on . . . . . . . . . . . . . . . . . . . . . . 3.1.1. Aplicaci´on parcial . . . . . . . . . . . . . . . 3.1.2. Secciones . . . . . . . . . . . . . . . . . . . . 3.1.3. Funciones de orden superior . . . . . . . . . . 3.1.4. Una funci´on de orden superior sobre naturales 3.2. Polimorfismo . . . . . . . . . . . . . . . . . . . . . . . 3.2.1. La composici´on de funciones . . . . . . . . . 3.2.2. Otras funciones polim´orficas . . . . . . . . . . 3.2.3. Polimorfismo en listas . . . . . . . . . . . . . 3.2.4. Polimorfismo en tuplas . . . . . . . . . . . . . 3.2.5. Un iterador polim´orfico sobre los naturales . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

49 49 51 54 56 58 60 62 65 67 69 70

4. Definici´on de tipos 4.1. Sin´onimos de tipo . . . . . . . . . . . . . . . . 4.2. Definici´on de tipos de datos . . . . . . . . . . . 4.2.1. Tipos enumerados . . . . . . . . . . . 4.2.2. Uniones . . . . . . . . . . . . . . . . . 4.2.3. Productos . . . . . . . . . . . . . . . . 4.2.4. Tipos recursivos . . . . . . . . . . . . 4.2.5. Tipos parametrizados (o polim´orficos) . 4.2.6. Definiciones newtype . . . . . . . . . 4.3. Propiedades de funciones . . . . . . . . . . . . 4.3.1. La propiedad universal de foldNat . . 4.4. Sobrecarga y polimorfismo restringido . . . . . 4.4.1. Un ejemplo de sobrecarga . . . . . . . 4.5. Ejercicios . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

71 . 71 . 72 . 72 . 73 . 74 . 78 . 87 . 89 . 90 . 97 . 99 . 101 . 103

2.7. 2.8. 2.9. 2.10. 2.11. 2.12. 2.13. 2.14. 2.15.

2.6.2. Patrones para listas . . . . . . . . . 2.6.3. Patrones para tuplas . . . . . . . . 2.6.4. Patrones aritm´eticos . . . . . . . . 2.6.5. Patrones nombrados o seud´onimos 2.6.6. El patr´on subrayado . . . . . . . . 2.6.7. Errores comunes . . . . . . . . . . 2.6.8. Patrones y evaluaci´on perezosa . . Expresiones case . . . . . . . . . . . . . . La funci´on error . . . . . . . . . . . . . . . Funciones a trozos . . . . . . . . . . . . . . Expresiones condicionales . . . . . . . . . . Definiciones locales . . . . . . . . . . . . . Expresiones lambda . . . . . . . . . . . . . Sangrado . . . . . . . . . . . . . . . . . . . ´ Ambitos y m´odulos . . . . . . . . . . . . . Ejercicios . . . . . . . . . . . . . . . . . .

c ITES-Paraninfo °

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

´Indice general

VII

5. El sistema de clases de H ASKELL 5.1. Tipos y clases de tipos. Jerarqu´ıa de clases . . . . . . . . . 5.1.1. El sistema de clases . . . . . . . . . . . . . . . . 5.1.2. Declaraci´on de clase . . . . . . . . . . . . . . . . 5.1.3. La clase Eqde P RELUDE . . . . . . . . . . . . . . 5.2. Contextos . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1. Instancias param´etricas . . . . . . . . . . . . . . 5.3. Subclases. La clase Ord de P RELUDE . . . . . . . . . . . 5.3.1. Un ejemplo: los enteros m´odulo n . . . . . . . . . 5.3.2. Intersecci´on de clases . . . . . . . . . . . . . . . 5.4. Visualizando y leyendo datos. Read y Show . . . . . . . . 5.5. Las clases Num, Integral y Fractional de P RELUDE . . . 5.5.1. Los tipos num´ericos de H ASKELL . . . . . . . . 5.5.2. Ambig¨uedad en las constantes num´ericas . . . . . 5.5.3. Promoci´on num´erica . . . . . . . . . . . . . . . . 5.5.4. Ejemplo: los racionales como instancias gen´ericas 5.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

105 105 105 109 111 112 115 115 118 118 119 122 123 125 126 128 129

6. Programaci´on con listas 6.1. El tipo lista . . . . . . . . . . . . . . . . . . . . . 6.1.1. Secuencias aritm´eticas. La clase Enum . 6.2. Concatenaci´on de listas . . . . . . . . . . . . . . 6.3. Inducci´on sobre listas . . . . . . . . . . . . . . . 6.4. Selectores . . . . . . . . . . . . . . . . . . . . . 6.5. Emparejando listas . . . . . . . . . . . . . . . . . 6.6. Aplicando una funci´on a los elementos de una lista 6.7. Filtros . . . . . . . . . . . . . . . . . . . . . . . 6.8. Listas por comprensi´on . . . . . . . . . . . . . . 6.8.1. Sem´antica de listas por comprensi´on . . 6.9. Plegado de listas . . . . . . . . . . . . . . . . . . 6.9.1. foldr . . . . . . . . . . . . . . . . . . . 6.9.2. La propiedad universal de foldr . . . . . 6.9.3. foldl . . . . . . . . . . . . . . . . . . . 6.10. Ordenaci´on de listas . . . . . . . . . . . . . . . . 6.10.1. Ordenaci´on por inserci´on . . . . . . . . 6.10.2. Ordenaci´on por mezcla . . . . . . . . . . 6.10.3. Ordenaci´on r´apida . . . . . . . . . . . . 6.11. Problemas combinatorios . . . . . . . . . . . . . 6.11.1. Los segmentos iniciales de una lista . . . 6.11.2. Los segmentos consecutivos de una lista 6.11.3. Permutaciones de una lista . . . . . . . . 6.12. Otras funciones predefinidas . . . . . . . . . . . . 6.13. Ejercicios . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

131 131 132 134 136 137 140 141 142 144 147 148 148 151 153 154 155 156 158 159 159 160 161 162 164

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

c ITES-Paraninfo °

´Indice general

VIII

7. Entrada y salida 7.1. Operaciones de entrada y salida . . . . . . . . . . 7.1.1. El problema de la entrada y salida . . . . 7.1.2. El tipo IO . . . . . . . . . . . . . . . . 7.1.3. Excepciones . . . . . . . . . . . . . . . 7.2. Un formateador de textos . . . . . . . . . . . . . 7.2.1. Una implementaci´on ineficiente . . . . . 7.2.2. Una implementaci´on eficiente . . . . . . 7.2.3. Utilidades para el manejo de documentos 7.2.4. Una clase de tipos documentables . . . . 7.2.5. Ejemplos . . . . . . . . . . . . . . . . .

II

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

Programaci´on avanzada

8. Evaluaci´on perezosa. Redes de procesos 8.1. Evaluaci´on perezosa . . . . . . . . . . . . . . . . . . . . . 8.1.1. Argumentos estrictos . . . . . . . . . . . . . . . . 8.1.2. Procesando estructuras infinitas en forma perezosa 8.2. Listas parciales y listas infinitas . . . . . . . . . . . . . . . 8.2.1. Aproximaciones o listas parciales . . . . . . . . . 8.2.2. Inducci´on sobre listas parciales . . . . . . . . . . 8.3. Redes finitas de procesos . . . . . . . . . . . . . . . . . . 8.3.1. La criba de Erat´ostenes . . . . . . . . . . . . . . 8.3.2. El tri´angulo de Pascal . . . . . . . . . . . . . . . 8.3.3. Procesos con varias entradas . . . . . . . . . . . . 8.3.4. La lista de factoriales . . . . . . . . . . . . . . . . 8.3.5. Los n´umeros de Fibonacci . . . . . . . . . . . . . 8.3.6. Sucesiones gen´ericas . . . . . . . . . . . . . . . . 8.3.7. Los n´umeros de Hamming . . . . . . . . . . . . . 8.4. Sucesiones contadoras . . . . . . . . . . . . . . . . . . . . 8.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . .

169 169 169 170 172 174 175 177 179 179 180

183 . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

185 185 185 186 189 189 190 191 193 195 196 196 198 199 202 203 207

9. Programaci´on con a´ rboles y grafos ´ 9.1. Arboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.1. Funciones de orden superior sobre a´ rboles . . . . . . . ´ 9.2. Arboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 9.2.1. Arboles binarios de b´usqueda . . . . . . . . . . . . . . 9.2.2. Funciones de orden superior para a´ rboles binarios . . . 9.2.3. Inducci´on para a´ rboles binarios . . . . . . . . . . . . . 9.3. Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3.1. Una implementaci´on ineficiente . . . . . . . . . . . . . 9.3.2. Una implementaci´on eficiente . . . . . . . . . . . . . . 9.4. Grafos y b´usqueda en grafos . . . . . . . . . . . . . . . . . . . . 9.4.1. B´usqueda en anchura y en profundidad . . . . . . . . . 9.4.2. Los grafos como instancias de una clase uniparam´etrica

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

211 211 213 215 215 219 220 222 222 224 226 227 229

c ITES-Paraninfo °

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

´Indice general 9.5.

9.6.

IX

Grafos con pesos . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.5.1. Grafos con pesos como instancias de clases biparam´etricas 9.5.2. Una clase H ASKELL para grafos con pesos . . . . . . . . Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

232 232 234 236

10. Programaci´on modular y tipos abstractos de datos 10.1. M´odulos . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2. Bibliotecas estandarizadas . . . . . . . . . . . . . . . . . 10.3. Declaraciones de m´odulos . . . . . . . . . . . . . . . . . 10.4. Importaci´on . . . . . . . . . . . . . . . . . . . . . . . . 10.4.1. Importaci´on cualificada . . . . . . . . . . . . . 10.5. Tipos abstractos de datos . . . . . . . . . . . . . . . . . 10.6. Representaci´on . . . . . . . . . . . . . . . . . . . . . . . 10.6.1. Representaci´on con una interfaz no sobrecargada 10.6.2. Representaci´on con una interfaz sobrecargada . . 10.7. El TAD Conjunto (Conjunto) . . . . . . . . . . . . . . . 10.8. El TAD Lista Ordenada (OrdLista) . . . . . . . . . . . . 10.9. El TAD Diccionario (Diccionario) . . . . . . . . . . . . 10.10. Un ´ındice KWIC (KeyWord In Context) . . . . . . . . . 10.10.1. Datos del problema . . . . . . . . . . . . . . . . 10.10.2. La funci´on kwic . . . . . . . . . . . . . . . . . 10.10.3. Algunas funciones y sin´onimos de tipos u´ tiles . 10.10.4. La funci´on creaNoClaves . . . . . . . . . . . . 10.10.5. Modelo de datos para la resoluci´on . . . . . . . 10.10.6. La funci´on kwic 0 . . . . . . . . . . . . . . . . . 10.11. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

243 243 243 243 245 246 247 247 247 249 253 254 255 257 258 259 259 261 261 262 264

11. Programaci´on con m´onadas 11.1. Concepto de m´onada . . . . . . . . . . . . . . . . 11.2. Clases de constructores de tipos . . . . . . . . . . 11.2.1. La clase Functor . . . . . . . . . . . . . 11.2.2. La clase Monad . . . . . . . . . . . . . 11.2.3. La clase MonadPlus . . . . . . . . . . . 11.3. Interpretaci´on de las propiedades . . . . . . . . . 11.3.1. Interpretaci´on del operador (>>=) . . . 11.4. Relaci´on entre funtor y m´onada . . . . . . . . . . 11.5. La notaci´on do . . . . . . . . . . . . . . . . . . . 11.6. Ejemplos de m´onadas . . . . . . . . . . . . . . . 11.6.1. La m´onada identidad . . . . . . . . . . . 11.6.2. La m´onada escritora . . . . . . . . . . . 11.6.3. La m´onada lectora . . . . . . . . . . . . 11.6.4. La m´onada de transformadores de estado 11.6.5. La lista como m´onada indeterminista . . 11.6.6. La m´onada error . . . . . . . . . . . . . 11.7. Operaciones con m´onadas . . . . . . . . . . . . . 11.7.1. Combinando m´onadas . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

265 265 266 266 269 272 273 276 277 280 283 283 284 286 288 291 292 296 297

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

c ITES-Paraninfo °

´Indice general

X

11.7.2. Transformadores mon´adicos . . . . . . . . . . . . . . . . . . 298 11.8. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

III

Aplicaciones

303

12. Algoritmos num´ericos programados funcionalmente 12.1. Introducci´on . . . . . . . . . . . . . . . . . . . 12.2. B´usqueda de puntos fijos . . . . . . . . . . . . 12.3. Extrapolaci´on por paso al l´ımite . . . . . . . . . ´ 12.4. Algebra lineal num´erica . . . . . . . . . . . . . 12.5. Series de potencias . . . . . . . . . . . . . . . . 12.6. Ejercicios . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

305 305 305 308 312 314 316

13. Puzzles y solitarios 13.1. Algunos problemas combinatorios . . . . . . . . . . . . 13.1.1. El producto m´aximo con un conjunto de d´ıgitos . 13.1.2. El problema de las vasijas . . . . . . . . . . . . 13.1.3. El problema de los can´ıbales y los misioneros . . 13.1.4. El solitario de Abreu . . . . . . . . . . . . . . . 13.2. La sopa de letras . . . . . . . . . . . . . . . . . . . . . . 13.2.1. Un esbozo de la soluci´on . . . . . . . . . . . . . 13.2.2. Buscando las apariciones de una palabra . . . . 13.2.3. Movimiento de matrices y lecturas de l´ıneas . . 13.3. El problema de las ocho reinas . . . . . . . . . . . . . . 13.3.1. Soluciones mediante listas por comprensi´on . . 13.3.2. Soluci´on mediante b´usqueda en grafos . . . . . 13.3.3. Grafos ac´ıclicos . . . . . . . . . . . . . . . . . 13.4. Programaci´on funcional estilo P ROLOG . . . . . . . . . . 13.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

319 319 319 320 322 324 327 327 329 330 333 333 336 338 339 342

14. Analizadores 14.1. Analizadores y la clase Read . . . . . 14.1.1. Gram´aticas y la notaci´on BNF 14.1.2. El tipo Read . . . . . . . . . 14.1.3. La clase Read . . . . . . . . 14.2. Analizadores mon´adicos . . . . . . . . 14.2.1. Secuenciaci´on . . . . . . . . 14.2.2. Alternancia . . . . . . . . . . 14.2.3. Filtros . . . . . . . . . . . . 14.2.4. Iteraci´on . . . . . . . . . . . 14.2.5. Elecci´on parcial . . . . . . . 14.2.6. Un analizador para t´erminos . 14.3. Ejercicios . . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

345 345 346 347 356 357 358 359 360 361 362 363 366

c ITES-Paraninfo °

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

´Indice general

XI

15. Simulaci´on 15.1. Generaci´on de aleatorios por congruencias . . . . . . . . . 15.1.1. Programando secuencias pseudo-aleatorias . . . . 15.1.2. Algunos resultados te´oricos . . . . . . . . . . . . 15.2. Simulaci´on en el juego del p´oquer . . . . . . . . . . . . . . 15.2.1. Generando un mazo de cartas . . . . . . . . . . . 15.2.2. B´usqueda de ciertas jugadas: parejas, tr´ıos, etc. . . 15.2.3. Contando todas las jugadas . . . . . . . . . . . . 15.3. Obteniendo semillas y aleatorios a trav´es del sistema . . . . 15.3.1. Un modelo mon´adico para la simulaci´on . . . . . 15.4. El juego de la loter´ıa primitiva . . . . . . . . . . . . . . . . 15.4.1. Realizando escrutinios . . . . . . . . . . . . . . . 15.4.2. Generaci´on de sorteos . . . . . . . . . . . . . . . 15.4.3. Estudio estad´ıstico de ciertas combinaciones . . . 15.4.4. Descripci´on mon´adica del juego de la primitiva . . 15.5. Simulaci´on mon´adica de juegos con dados . . . . . . . . . 15.5.1. Mezclando valores producidos por varias acciones 15.5.2. Plegando valores mon´adicos . . . . . . . . . . . . 15.5.3. Repetici´on de varias tiradas con varios dados . . . 15.5.4. Contabilizando jugadas . . . . . . . . . . . . . .

IV

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

Aspectos te´oricos

369 369 370 373 374 374 375 376 379 380 383 383 384 385 387 388 389 389 391 392

395

16. T´ecnicas de programaci´on y transformaciones de programas 16.1. Inducci´on estructural . . . . . . . . . . . . . . . . . . . . . . . . 16.2. Par´ametros acumuladores . . . . . . . . . . . . . . . . . . . . . . 16.2.1. Los n´umeros de Fibonacci . . . . . . . . . . . . . . . . . 16.2.2. C´alculo del factorial de un natural . . . . . . . . . . . . . 16.2.3. Plegados estrictos . . . . . . . . . . . . . . . . . . . . . 16.3. Transformaci´on de programas. El modelo desplegar/plegar . . . . 16.3.1. Un ejemplo sencillo de transformaci´on . . . . . . . . . . 16.3.2. Las reglas desplegar/plegar . . . . . . . . . . . . . . . . 16.3.3. Reducci´on de la complejidad por transformaci´on . . . . . 16.3.4. Correcci´on parcial de los programas transformados . . . . 16.4. Programas a partir de especificaciones . . . . . . . . . . . . . . . 16.4.1. Especificaciones ejecutables . . . . . . . . . . . . . . . . 16.4.2. Especificaciones no ejecutables . . . . . . . . . . . . . . 16.4.3. Transformaci´on de una especificaci´on no ejecutable . . . 16.5. Sem´antica denotacional de un lenguaje imperativo . . . . . . . . . 16.5.1. Representaci´on de entornos con tuplas . . . . . . . . . . 16.5.2. Representaci´on de entornos con funciones . . . . . . . . 16.5.3. El lenguaje imperativo de Dijkstra . . . . . . . . . . . . . 16.5.4. Una sem´antica determinista para el lenguaje de Dijkstra . 16.5.5. Una sem´antica indeterminista para el lenguaje de Dijkstra 16.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . .

397 397 405 405 410 414 417 417 418 420 425 425 426 426 427 430 432 434 437 439 441 443

c ITES-Paraninfo °

XII

´Indice general

17. Introducci´on al λ-c´alculo 17.1. Sintaxis del lambda c´alculo . . . . . . . . . . . . . . . . . . . . . 17.2. δ-reducci´on y β-reducci´on . . . . . . . . . . . . . . . . . . . . . . 17.2.1. λ-teor´ıas . . . . . . . . . . . . . . . . . . . . . . . . . . 17.2.2. Eta-conversi´on y extensionalidad . . . . . . . . . . . . . 17.2.3. Reducci´on generada por un programa . . . . . . . . . . . 17.3. Formas normales. Teoremas de Church-Rosser . . . . . . . . . . . ´ 17.4. Ordenes de reducci´on. Teorema de estandarizaci´on . . . . . . . . . 17.5. Lambda definibilidad . . . . . . . . . . . . . . . . . . . . . . . . 17.5.1. Operaciones l´ogicas . . . . . . . . . . . . . . . . . . . . 17.5.2. Computabilidad . . . . . . . . . . . . . . . . . . . . . . 17.5.3. Puntos fijos y recursi´on . . . . . . . . . . . . . . . . . . 17.5.4. Listas en el λC . . . . . . . . . . . . . . . . . . . . . . . 17.6. Los sistemas de tipos de Church y de Curry . . . . . . . . . . . . . 17.6.1. Propiedades del sistema λ→ Curry . . . . . . . . . . . . . 17.6.2. La correspondencia de Howard-Curry-de Bruijn . . . . . 17.7. Ejemplos pr´acticos de inferencia de tipos . . . . . . . . . . . . . . 17.7.1. Caso de un u´ nico argumento . . . . . . . . . . . . . . . . 17.7.2. Caso de varios argumentos . . . . . . . . . . . . . . . . . 17.7.3. Caso en que aparecen otras variables predefinidas . . . . 17.8. Inferencia de tipos en presencia de recursi´on . . . . . . . . . . . . 17.9. Inferencia de tipos en presencia de patrones . . . . . . . . . . . . 17.10. Reglas elementales para inferencia de tipos . . . . . . . . . . . . . 17.11. El λ-c´alculo polim´orfico . . . . . . . . . . . . . . . . . . . . . . . 17.11.1. Inferencia de tipos en presencia de polimorfismo . . . . . 17.11.2. Un teorema de parametricidad para funciones polim´orficas

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

451 451 453 457 459 460 461 465 468 469 469 471 473 474 475 478 478 479 480 482 484 487 490 492 494 496

Bibliograf´ıa

499

´ Indice alfab´etico

503

c ITES-Paraninfo °

´INDICE DE FIGURAS

1.1. 1.2.

Representaci´on perezosa de la funci´on doble . . . . . . . . . . . . . . Reducci´on perezosa de doble (doble 3) . . . . . . . . . . . . . . . . .

10 10

2.1. 2.2. 2.3.

Asociatividad y prioridad de los operadores predefinidos . . . . . . . . Sangrando una declaraci´on . . . . . . . . . . . . . . . . . . . . . . . Sangrando dos declaraciones . . . . . . . . . . . . . . . . . . . . . .

26 44 44

3.1. 3.2. 3.3. 3.4.

Aplicaciones parciales . . . . La funci´on unaVez . . . . . La funci´on dosVeces . . . . La composici´on de funciones

. . . .

52 61 62 63

4.1.

C´alculo de esPar usando foldNat

. . . . . . . . . . . . . . . . . . .

86

5.1. 5.2. 5.3.

Jerarqu´ıa de clases de P RELUDE . . . . . . . . . . . . . . . . . . . . 108 Instancias H ASKELL estandarizadas para los tipos de P RELUDE . . . . 109 La clase Ord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

6.1. 6.2. 6.3. 6.4. 6.5. 6.6. 6.7. 6.8.

La clase Enum . . . . . . . . . . . . . . . head , tail , init y last . . . . . . . . . . . . take, drop y (!!) . . . . . . . . . . . . . . . Reducci´on de foldr f z [x1 , . . . , xn−1 , xn ] Reducci´on de foldr 1 f [x1 , . . . , xn−1 , xn ] . Reducci´on de foldl f z [x1 , . . . , xn−1 , xn ] . Ordenaci´on por mezcla . . . . . . . . . . . Ordenaci´on r´apida . . . . . . . . . . . . . .

7.1. 7.2.

Di´alogos con pretty printer . . . . . . . . . . . . . . . . . . . . . . . 181 Di´alogos con pretty printer . . . . . . . . . . . . . . . . . . . . . . . 181

8.1. 8.2. 8.3. 8.4. 8.5. 8.6. 8.7.

La funci´on incr . . . . . . . . . . . . . . . . . . Red para la evaluaci´on de los enteros positivos . . Red de procesos para sucesiones . . . . . . . . . Red de procesos para la criba de Erat´ostenes . . . Red para el tri´angulo de Pascal . . . . . . . . . . Red de procesos para la lista de factoriales . . . . Red para el c´omputo de los n´umeros de Fibonacci

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . . . . .

. . . .

. . . . . . . .

. . . . . . .

. . . .

. . . . . . . .

. . . . . . .

. . . .

. . . . . . . .

. . . . . . .

. . . .

. . . . . . . .

. . . . . . .

. . . .

. . . . . . . .

. . . . . . .

. . . .

. . . . . . . .

. . . . . . .

. . . .

. . . . . . . .

. . . . . . .

. . . .

. . . . . . . .

. . . . . . .

. . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

132 138 139 150 151 153 157 158

192 192 193 195 196 197 199

´Indice de figuras

XIV

8.8. Red para el c´alculo de la sucesi´on xn . . . . . . . . . . . . . . . . . . 201 8.9. Red para el c´omputo de los n´umeros de Hamming . . . . . . . . . . . 202 8.10. Red de procesos para los pares de naturales . . . . . . . . . . . . . . . 208 9.1. 9.2. 9.3. 9.4. 9.5. 9.6. 9.7. 9.8. 9.9. 9.10. 9.11.

Un a´ rbol con 7 elementos . . . Un a´ rbol ordenado . . . . . . . Eliminaci´on de un dato . . . . ´ Arbol para creaArray [0..7] . . Un grafo . . . . . . . . . . . . Otro grafo . . . . . . . . . . . ´ Arbol de visitas en profundidad ´ Arbol de visitas en anchura . . Un grafo sencillo . . . . . . . . Un grafo con pesos . . . . . . Un diccionario . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

211 216 217 225 227 227 228 228 231 235 238

10.1. Cabecera del m´odulo Conjunto . . . . . . . . . . . . . . . . . . . . . 253 11.1. Definici´on de (>>=) . . . . . . . . . . . . . 11.2. Propiedad (m1) . . . . . . . . . . . . . . . . 11.3. Propiedad (m2) . . . . . . . . . . . . . . . . 11.4. Propiedad (k1) . . . . . . . . . . . . . . . . . 11.5. Propiedad (k2) . . . . . . . . . . . . . . . . . 11.6. Propiedad (k3). Primera funci´on . . . . . . . 11.7. Propiedad (k3). Segunda funci´on . . . . . . . 11.8. C´omputos con (>>=) . . . . . . . . . . . . . 11.9. C´omputos con (>>=) gr´aficamente . . . . . 11.10. Definici´on de fmap a trav´es de una m´onada . 11.11. Definici´on de join a partir de una m´onada . . 11.12. Definici´on de (>>=) a partir de join y fmap 11.13. El operador (>>=) de la m´onada Lectora . . 11.14. Un transformador de estados . . . . . . . . . 11.15. (>>=) para transformadores de estados . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

266 273 273 274 274 275 276 277 277 278 278 279 287 289 289

12.1. C´alculo de la ra´ız n-´esima por el m´etodo de Newton-Raphson . . . . . 307 12.2. Traspuesta de una matriz . . . . . . . . . . . . . . . . . . . . . . . . 313 13.1. El problema de las vasijas . . . . . . . . . . . . . . . . . . . . . 13.2. El problema de los can´ıbales y misioneros . . . . . . . . . . . . 13.3. Tablero de cuatro filas para el solitario de Abreu. Un movimiento 13.4. Posici´on inicial y final del ocho-puzzle. Un movimiento . . . . . 13.5. Direcciones en la lectura . . . . . . . . . . . . . . . . . . . . . . 13.6. Reconstrucci´on de las diagonales . . . . . . . . . . . . . . . . . 13.7. noAtaca 2 [5, 1, 4] =⇒ True . . . . . . . . . . . . . . . . . . . 13.8. noAtaca 3 [5, 1, 4] =⇒ False . . . . . . . . . . . . . . . . . . . 13.9. Dos reinas que se atacan . . . . . . . . . . . . . . . . . . . . . . 13.10. El problema de las ocho reinas . . . . . . . . . . . . . . . . . . c ITES-Paraninfo °

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

321 323 325 326 331 332 334 334 335 337

´Indice de figuras 13.11. Las torres de Hanoi . . . . . . . . . . . . . . . . . 13.12. El problema de las Torres de Hanoi con cuatro torres 13.13. El tablero del solitario . . . . . . . . . . . . . . . . 13.14. Un cuadrado m´agico . . . . . . . . . . . . . . . . . 13.15. El problema de los tres sombreros . . . . . . . . . . 13.16. Los cuatro caballos . . . . . . . . . . . . . . . . . 13.17. El problema de los trenes . . . . . . . . . . . . . . 13.18. Un pol´ıgono . . . . . . . . . . . . . . . . . . . . . 13.19. La v´ıa . . . . . . . . . . . . . . . . . . . . . . . .

XV

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

338 339 339 340 340 342 343 343 343

17.1. Algunos t´erminos notables . . . . . . . . . . . . . . . . . . . . . . . 468 17.2. El sistema de tipos de Curry . . . . . . . . . . . . . . . . . . . . . . . 475 17.3. El λ-c´alculo polim´orfico . . . . . . . . . . . . . . . . . . . . . . . . . 493

c ITES-Paraninfo °