PDF de programación - Ejercicios de programación funcional con Haskell

Ejercicios de programación funcional con

Haskell

José A. Alonso Jiménez

Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
Sevilla, 8 de Agosto de 2007 (Versión de 1 de agosto de 2008)

2

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 especificada
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 licencia 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

I Programación básica

9

.

.

.

.

.

.

.

.

.

.

1. Introducción a la programación funcional

. .

11
1.1. Factorial
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2. Número de combinaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3. Comprobación de número impar . . . . . . . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4. Cuadrado . .
.
1.5. Suma de cuadrados .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6. Raices de ecuaciones de segundo grado . . . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
.
1.7. Valor absoluto .
.
.
.
1.8. Signo .
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
. .
1.9. Conjunción . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
. . . . . . . . . . . . . . . . . . . . . . . . . 19
1.10. Anterior de un número natural
.
1.11. Potencia . .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.12. Función identidad .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

. .

.
.
.

.
.
.

.
.
.

.
.

.
.

.
.

.

.

.

.

2. Números y funciones
.

.

.

.

.

.

.

.

.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.
. .

.
.
Inverso . .

23
2.1. Casi igual .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2. Siguiente de un número . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3. Doble .
.
.
.
.
2.4. Mitad .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
. .
2.5.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6. Potencia de dos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.7. Reconocimiento de números positivos . . . . . . . . . . . . . . . . . . . . . 28
2.8. Aplicación de una función a los elementos de una lista . . . . . . . . . . . 29
2.9. Filtrado mediante una propiedad . . . . . . . . . . . . . . . . . . . . . . . . 30
2.10. Suma de los elementos de una lista . . . . . . . . . . . . . . . . . . . . . . . 31
2.11. Producto de los elementos de una lista . . . . . . . . . . . . . . . . . . . . . 31
2.12. Conjunción sobre una lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.13. Disyunción sobre una lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.14. Plegado por la derecha .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.15. Plegado por la izquierda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3

4

Índice general

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.16. Resultados acumulados
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.17. Lista de factoriales
. .
2.18. Iteración hasta–que . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.19. Composición de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.20. Intercambio de orden de argumentos . . . . . . . . . . . . . . . . . . . . . . 38
2.21. Relación de divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.22. Lista de divisores de un número . . . . . . . . . . . . . . . . . . . . . . . . 39
2.23. Comprobación de número primo . . . . . . . . . . . . . . . . . . . . . . . . 39
2.24. Lista de primos . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.25. Cálculo del día de la semana . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.26. Diferenciación numérica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.27. Cálculo de la raíz cuadrada . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.28. Cálculo de ceros de una función . . . . . . . . . . . . . . . . . . . . . . . . . 43

. .

3. Estructuras de datos

.

.

.

.

.

.

.

.
.
.

45
3.1. Relación de igualdad entre listas . . . . . . . . . . . . . . . . . . . . . . . . 47
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2. Concatenación de listas .
3.3. Concatenación de una lista de listas
. . . . . . . . . . . . . . . . . . . . . . 48
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4. Cabeza de una lista .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
.
3.5. Resto de una lista .
3.6. Último elemento .
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.7. Lista sin el último elemento . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.8. Segmento inicial .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.9. Segmento inicial filtrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.10. Segmento final .
.
3.11. Segmento final filtrado .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.12. N–ésimo elemento de una lista . . . . . . . . . . . . . . . . . . . . . . . . . 54
.
3.13. Inversa de una lista .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
.
3.14. Longitud de una lista .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.15. Comprobación de pertenencia de un elemento a una lista . . . . . . . . . . 57
3.16. Comprobación de no pertenencia de un elemento a una lista . . . . . . . . 58
3.17. Comprobación de que una lista está ordenada . . . . . . . . . . . . . . . . 60
3.18. Comprobación de la igualdad de conjuntos . . . . . . . . . . . . . . . . . . 61
3.19. Inserción ordenada de un elemento en una lista . . . . . . . . . . . . . . . . 62
3.20. Ordenación por inserción . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.21. Mínimo elemento de una lista . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.22. Mezcla de dos listas ordenadas . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.23. Ordenación por mezcla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.24. Dígito correspondiente a un carácter numérico . . . . . . . . . . . . . . . . 67
3.25. Carácter correspondiente a un dígito . . . . . . . . . . . . . . . . . . . . . . 68
3.26. Lista infinita de números . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Índice general

5

3.27. Lista con un elemento repetido . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.28. Lista con un elemento repetido un número dado de veces . . . . . . . . . . 70
3.29. Iteración de una función . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.30. Conversión de número entero a cadena . . . . . . . . . . . . . . . . . . . . 71
3.31. Cálculo de primos mediante la criba de Erastótenes . . . . . . . . . . . . . 72
3.32. Comprobación de que todos los elementos son pares . . . . . . . . . . . . . 73
3.33. Comprobación de que todos los elementos son impares . . . . . . . . . . . 74
3.34. Triángulos numéricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.35. Posición de un elemento en una lista . . . . . . . . . . . . . . . . . . . . . . 76
3.36. Ordenación rápida . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.37. Primera componente de un par . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.38. Segunda componente de un par . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.39. Componentes de una terna . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.40. Creación de variables a partir de pares . . . . . . . . . . . . . . . . . . . . . 79
3.41. División de una lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.42. Sucesión de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.43. Incremento con el mínimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.44. Longitud de camino entre puntos bidimensionales . . . . . . . . . . . . . . 83
3.45. Números racionales . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.46. Máximo común divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.47. Búsqueda en una lista de asociación . . . . . . . . . . . . . . . . . . . . . . 87
3.48. Emparejamiento de dos listas . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.49. Emparejamiento funcional de dos listas . . . . . . . . . . . . . . . . . . . . 89
. .
3.50. Currificación .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.51. Funciones sobre árboles
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.52. Búsqueda en lista ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.53. Movimiento según las direcciones
. . . . . . . . . . . . . . . . . . . . . . . 94
3.54. Los racionales como tipo abstracto de datos . . . . . . . . . . . . . . . . . . 94

.

.

.

. .