PDF de programación - Temas de programación funcional

Imágen de pdf Temas de programación funcional

Temas de programación funcionalgráfica de visualizaciones

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 . . . . . . .
  • Links de descarga
http://lwp-l.com/pdf10241

Comentarios de: Temas de programación funcional (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad