Publicado el 7 de Abril del 2018
501 visualizaciones desde el 7 de Abril del 2018
1,2 MB
339 paginas
Creado hace 12a (24/09/2011)
Temas de “Programación funcional”
(curso 2011–12)
José A. Alonso Jiménez
Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
Sevilla, 24 de Septiembre de 2011 (versión de 24 de septiembre de 2011)
Esta obra está bajo una licencia Reconocimiento–NoComercial–CompartirIgual 2.5 Spain
de Creative Commons.
Se permite:
copiar, distribuir y comunicar públicamente la obra
hacer obras derivadas
Bajo las condiciones siguientes:
Reconocimiento. Debe reconocer los créditos de la obra de la manera espe-
cificada por el autor.
No comercial. No puede utilizar esta obra para fines comerciales.
Compartir bajo la misma licencia. Si altera o transforma esta obra, o genera
una obra derivada, sólo puede distribuir la obra generada bajo una licencia
idéntica a ésta.
Al reutilizar o distribuir la obra, tiene que dejar bien claro los términos de la licen-
cia de esta obra.
Alguna de estas condiciones puede no aplicarse si se obtiene el permiso del titular
de los derechos de autor.
Esto es un resumen del texto legal (la licencia completa). Para ver una copia de esta
licencia, visite http://creativecommons.org/licenses/by-nc-sa/2.5/es/ o envie una
carta a Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.
Índice general
1. Introducción a la programación funcional
.
.
.
.
.
.
.
1.1. Funciones
.
1.2. Programación funcional
1.3. Rasgos característicos de Haskell
1.4. Antecedentes históricos
1.5. Presentación de Haskell
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
5
7
8
9
9
.
.
.
.
2. Introducción a la programación con Haskell
2.1. El sistema GHC .
2.2.
13
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Iniciación a GHC .
Inicio de sesión con GHCi . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1.
2.2.2. Cálculo aritmético . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.3. Cálculo con listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.4. Cálculos con errores . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3. Aplicación de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4. Guiones Haskell .
2.4.1. El primer guión Haskell
. . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.2. Nombres de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.3. La regla del sangrado . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.4. Comentarios en Haskell
. . . . . . . . . . . . . . . . . . . . . . . . . 19
.
.
.
3. Tipos y clases
. .
21
3.1. Conceptos básicos sobre tipos . . . . . . . . . . . . . . . . . . . . . . . . . . 21
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2. Tipos básicos .
.
.
.
3.3. Tipos compuestos .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.1. Tipos listas . .
3.3.2. Tipos tuplas .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.3. Tipos funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.4. Parcialización .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.5. Polimorfismo y sobrecarga . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.5.1. Tipos polimórficos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
.
.
.
.
.
3
4
Temas de programación funcional (2010–11)
3.5.2. Tipos sobrecargados . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.6. Clases básicas .
. .
. .
4. Definición de funciones
35
4.1. Definiciones por composición . . . . . . . . . . . . . . . . . . . . . . . . . . 35
. . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2. Definiciones con condicionales
. . . . . . . . . . . . . . . . . . . 36
4.3. Definiciones con ecuaciones con guardas
4.4. Definiciones con equiparación de patrones
. . . . . . . . . . . . . . . . . . 36
4.4.1. Constantes como patrones . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4.2. Variables como patrones . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4.3. Tuplas como patrones . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4.4. Listas como patrones . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4.5. Patrones enteros
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
.
4.5. Expresiones lambda .
.
4.6. Secciones .
. .
. .
.
.
.
.
.
.
.
.
.
.
.
.
5. Definiciones de listas por comprensión
43
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
. .
5.1. Generadores .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
.
5.2. Guardas
.
.
5.3. La función zip .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
.
5.4. Comprensión de cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.5. Cifrado César
5.5.1. Codificación y descodificación . . . . . . . . . . . . . . . . . . . . . 48
5.5.2. Análisis de frecuencias . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.5.3. Descifrado . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
. .
.
.
.
6. Funciones recursivas
53
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.1. Recursión numérica .
6.2. Recusión sobre lista .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.3. Recursión sobre varios argumentos . . . . . . . . . . . . . . . . . . . . . . . 57
6.4. Recursión múltiple .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.5. Recursión mutua .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
.
6.6. Heurísticas para las definiciones recursivas . . . . . . . . . . . . . . . . . . 59
.
.
.
.
.
.
.
.
7. Funciones de orden superior
63
7.1. Funciones de orden superior . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.2. Procesamiento de listas .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.2.1. La función map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.2.2. La función filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7.3. Función de plegado por la derecha: foldr . . . . . . . . . . . . . . . . . . . 66
7.4. Función de plegado por la izquierda: foldl . . . . . . . . . . . . . . . . . . 69
Índice general
5
7.5. Composición de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.6. Caso de estudio: Codificación binaria y transmisión de cadenas . . . . . . 71
7.6.1. Cambio de bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.6.2. Codificación y descodificación . . . . . . . . . . . . . . . . . . . . . 73
8. Razonamiento sobre programas
8.1. Razonamiento ecuacional
77
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.1.1. Cálculo con longitud . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.1.2. Propiedad de intercambia . . . . . . . . . . . . . . . . . . . . . . . 77
8.1.3.
Inversa de listas unitarias . . . . . . . . . . . . . . . . . . . . . . . . 78
8.1.4. Razonamiento ecuacional con análisis de casos . . . . . . . . . . . . 79
8.2. Razonamiento por inducción sobre los naturales . . . . . . . . . . . . . . . 79
8.2.1. Esquema de inducción sobre los naturales
. . . . . . . . . . . . . . 79
8.2.2. Ejemplo de inducción sobre los naturales . . . . . . . . . . . . . . . 80
. . . . . . . . . . . . . . . . . . . 81
8.3.1. Esquema de inducción sobre listas . . . . . . . . . . . . . . . . . . . 81
8.3.2. Asociatividad de ++ . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.3.3. [] es la identidad para ++ por la derecha . . . . . . . . . . . . . . . 82
8.3.4. Relación entre length y ++ . . . . . . . . . . . . . . . . . . . . . . . . 83
8.3.5. Relación entre take y drop . . . . . . . . . . . . . . . . . . . . . . . . 84
8.3.6. La concatenación de listas vacías es vacía . . . . . . . . . . . . . . . 85
8.4. Equivalencia de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
8.5. Propiedades de funciones de orden superior
. . . . . . . . . . . . . . . . . 87
8.3. Razonamiento por inducción sobre listas
9. Declaraciones de tipos y clases
91
9.1. Declaraciones de tipos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
9.2. Definiciones de tipos de datos . . . . . . . . . . . . . . . . . . . . . . . . . . 93
9.3. Definición de tipos recursivos . . . . . . . . . . . . . . . . . . . . . . . . . . 95
9.4. Sistema de decisión de tautologías . . . . . . . . . . . . . . . . . . . . . . . 99
9.5. Máquina abstracta de cálculo aritmético . . . . . . . . . . . . . . . . . . . . 102
9.6. Declaraciones de clases y de instancias . . . . . . . . . . . . . . . . . . . . . 104
10. Evaluación perezosa
.
.
109
10.1. Estrategias de evaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
10.2. Terminación .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
10.3. Número de reducciones
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
10.4. Estructuras infinitas .
.
.
10.5. Programación modular .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
.
10.6. Aplicación estricta .
.
.
.
6
Temas de programación funcional (2010–11)
11. Aplicaciones de programación funcional
119
11.1. El juego de cifras y letras . . . . . . .
Comentarios de: Temas de programación funcional (0)
No hay comentarios