PDF de programación - Piensa en Haskell (Ejercicios de programación funcional con Haskell)

Piensa en Haskell

(Ejercicios de programación funcional con Haskell)

José A. Alonso Jiménez
Ma José Hidalgo Doblado

Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
Sevilla, 10 de Julio de 2012 (Versión de 11 de octubre de 2012)

2

A mi amigo Felipe

Esta obra está bajo una licencia Reconocimiento–NoComercial–CompartirIgual 2.5 Spain
de Creative Commons.

3

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.

4

Índice general

I

Introducción a la programación funcional

19

1 Definiciones elementales de funciones

.
.

.
.

21
1.1 Media de 3 números .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.2
. . . . . . . . . . . . . . . . 23
Suma de euros de una colección de monedas
1.3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Volumen de la esfera .
1.4
Área de una corona circular
. . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.5
Última cifra de un número . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6 Máximo de 3 elementos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Disyunción excluyente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.7
1.8
Rotación de listas
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
.
1.9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Rango de una lista .
1.10 Reconocimiento de palíndromos . . . . . . . . . . . . . . . . . . . . . . . . 26
1.11 Elementos interiores de una lista . . . . . . . . . . . . . . . . . . . . . . . . 26
1.12 Finales de una lista .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Segmentos de una lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.13
1.14 Extremos de una lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.15 Mediano de 3 números . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.16
Igualdad y diferencia de 3 elementos . . . . . . . . . . . . . . . . . . . . . 28
1.17
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Igualdad de 4 elementos
1.18 Propiedad triangular
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.19 División segura .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.20 Disyunción excluyente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.21 Módulo de un vector
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.22 Rectángulo de área máxima . . . . . . . . . . . . . . . . . . . . . . . . . . 31
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.23 Puntos del plano .
1.23.1 Cuadrante de un punto . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.23.2 Intercambio de coordenadas . . . . . . . . . . . . . . . . . . . . . . 31

.

.

.

.

5

6

Índice general

.

1.24 Números complejos .

1.23.3 Punto simétrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.23.4 Distancia entre dos puntos . . . . . . . . . . . . . . . . . . . . . . . 32
1.23.5 Punto medio entre otros dos . . . . . . . . . . . . . . . . . . . . . . 32
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.24.1 Suma de dos números complejos . . . . . . . . . . . . . . . . . . . 33
1.24.2 Producto de dos números complejos . . . . . . . . . . . . . . . . . 33
1.24.3 Conjugado de un número complejo . . . . . . . . . . . . . . . . . . 33
1.25
Intercalación de pares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.26 Permutación cíclica de una lista . . . . . . . . . . . . . . . . . . . . . . . . 34
1.27 Mayor número de 2 cifras con dos dígitos dados
. . . . . . . . . . . . . . 34
1.28 Número de raíces de una ecuación cuadrática . . . . . . . . . . . . . . . . 35
1.29 Raíces de las ecuaciones cuadráticas
. . . . . . . . . . . . . . . . . . . . . 35
1.30 Área de un triángulo mediante la fórmula de Herón . . . . . . . . . . . . 36
. . . . . . . . . . . . . . . . . 36
1.31 Números racionales como pares de enteros
1.31.1 Forma reducida de un número racional . . . . . . . . . . . . . . . . 36
1.31.2 Suma de dos números racionales . . . . . . . . . . . . . . . . . . . 36
1.31.3 Producto de dos números racionales . . . . . . . . . . . . . . . . . 37
1.31.4 Igualdad de números racionales . . . . . . . . . . . . . . . . . . . . 37

2 Definiciones por comprensión

.

39
Suma de los cuadrados de los n primeros números . . . . . . . . . . . . . 40
2.1
Listas con un elemento replicado . . . . . . . . . . . . . . . . . . . . . . . 40
2.2
Triángulos aritméticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4 Números perfectos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.5 Números abundantes .
2.6
Problema 1 del proyecto Euler . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.7 Número de pares de naturales en un círculo . . . . . . . . . . . . . . . . . 44
2.8
Aproximación del número e . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.9
Aproximación del límite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.10 Cálculo del número π . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.11 Ternas pitagóricas .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.12 Problema 9 del Proyecto Euler . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.13 Producto escalar .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.14
Suma de pares de elementos consecutivos . . . . . . . . . . . . . . . . . . 50
2.15 Posiciones de un elemento en una lista . . . . . . . . . . . . . . . . . . . . 50
2.16 Representación densa de un polinomio representado dispersamente . . . 51
2.17 Producto cartesiano .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

.

.

.

.

.

.

Índice general

7

2.18 Consulta de bases de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3 Definiciones por recursión

.

.

.

.

55
Potencia de exponente natural . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1
Replicación de un elemento . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
Doble factorial
3.3
Algoritmo de Euclides del máximo común divisor
. . . . . . . . . . . . . 57
3.4
3.5 Menor número divisible por una sucesión de números . . . . . . . . . . . 58
3.6 Número de pasos para resolver el problema de las torres de Hanoi . . . . 59
3.7
Conjunción de una lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Pertenencia a una lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.8
3.9
Último elemento de una lista . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.10 Concatenación de una lista . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Selección de un elemento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.11
3.12
Selección de los primeros elementos . . . . . . . . . . . . . . . . . . . . . . 61
3.13
Intercalación de la media aritmética . . . . . . . . . . . . . . . . . . . . . . 62
3.14 Ordenación por mezcla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.14.1 Mezcla de listas ordenadas . . . . . . . . . . . . . . . . . . . . . . . 62
3.14.2 Mitades de una lista . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.14.3 Ordenación por mezcla . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.14.4 La ordenación por mezcla da listas ordenadas . . . . . . . . . . . . 63
3.14.5 La ordenación por mezcla da una permutación . . . . . . . . . . . 64
3.14.6 Determinación de permutaciones . . . . . . . . . . . . . . . . . . . 65

4 Definiciones por recursión y por comprensión

67
4.1
Suma de los cuadrados de los primeros números . . . . . . . . . . . . . . 68
4.2 Número de bloques de escaleras triangulares . . . . . . . . . . . . . . . . 70
4.3
Suma de los cuadrados de los impares entre los primeros números . . . . 71
Operaciones con los dígitos de los números . . . . . . . . . . . . . . . . . 72
4.4
4.4.1 Lista de los dígitos de un número . . . . . . . . . . . . . . . . . . . 72
4.4.2
Suma de los dígitos de un número . . . . . . . . . . . . . . . . . . 73
4.4.3 Decidir si es un dígito del número . . . . . . . . . . . . . . . . . . . 74
4.4.4 Número de dígitos de un número . . . . . . . . . . . . . . . . . . . 74
4.4.5 Número correspondiente a una lista de dígitos . . . . . . . . . . . 75
4.4.6 Concatenación de dos números . . . . . . . . . . . . . . . . . . . . 75
4.4.7 Primer dígito de un número . . . . . . . . . . . . . . . . . . . . . . 76
4.4.8 Último dígito de un número . . . . . . . . . . . . . . . . . . . . . . 77
4.4.9 Número con los dígitos invertidos
. . . . . . . . . . . . . . . . . . 78

8

Índice general

4.4.10 Decidir si un número es capicúa . . . . . . . . . . . . . . . . . . . . 79
4.4.11 Suma de los dígitos de 21000
. . . . . . . . . . . . . . . . . . . . . . 79
4.4.12 Primitivo de un número . . . . . . . . . . . . . . . . . . . . . . . . 80
4.4.13 Números con igual media de sus dígitos . . . . . . . . . . . . . . . 80
4.4.14 Números con dígitos