estudiante

Programaci´n Funcional
o

Jeroen Fokker

1996

Universidad de Utrecht
Departamento de Inform´tica
a
Traducci’on: Programa MEMI
Universidad Mayor de San Sim´n
o
Hielko R. Ophoff & Bernardo S´nchez J.
a
Revisi´n: Universidad Carlos III de Madrid
o
Carlos Delgado Kloos & Natividad Mart´
ınez Madrid

Programaci´n Funcional
o

c Copyright 1992–1996 Departamento de Inform´tica,Universidad de Utrecht
a
Este texto puede ser reproducido para fines educativos bajo las siguientes condiciones:
• que no se modifique ni reduzca el texto,
• que en especial no se elimine este mensaje,
• y que no se vendan las copias con fines lucrativos.

Primera edici´n: Septiembre 1992
o
Segunda edici´n: Agosto 1995
o
Segunda edici´n revisada: Marzo 1996
o

ii

´
Indice General
1Programaci´n Funcional 1
o
1.1 Lenguajes funcionales 1
1.1.1 Funciones 1
1.1.2 Lenguajes 1
1.2 El int´rprete de Gofer 2
e
1.2.1 Calcular expresiones 2
1.2.2 Definir funciones 4
1.2.3 Comandos del int´rprete 5
e
1.3 Funciones est´ndar 6
a
1.3.1 Operadores, funciones predefinidas y funciones primitivas
1.3.2 Nombres de funciones y operadores 7
1.3.3 Funciones sobre n´meros 8
u
1.3.4Funciones booleanas 9
1.3.5 Funciones sobre listas 10
1.3.6 Funciones de funciones 11
1.4 Definici´n de funciones 11
o
1.4.1 Definici´n por combinaci´n 11
o
o
1.4.2 Definici´n por distinci´n de casos 12
o
o
1.4.3 Definici´n por an´lisis de patrones 13
o
a
1.4.4 Definici´n por recursi´n o inducci´n 14
o
o
o
1.4.5 Indentaci´n y comentarios 15
o
1.5 Tipado 16
1.5.1 Clases de errores16
1.5.2 Expresiones de tipo 18
1.5.3 Polimorfismo 19
1.5.4 Funciones con m´s de un par´metro 20
a
a
1.5.5 Sobrecarga 20
Ejercicios 21
2 N´ meros y funciones 23
u
2.1 Operadores 23
2.1.1 Operadores como funciones y viceversa 23
2.1.2 Precedencias 23
2.1.3 Asociatividad 24
2.1.4 Definici´n de operadores 25
o
2.2 Currificaci´n 25
o
2.2.1 Instanciar parcialmente 25
2.2.2 Par´ntesis 26e
2.2.3 Secciones de operadores 27
2.3 Funciones como par´metros 27
a
2.3.1 Funciones sobre listas 27
2.3.2 Iteraci´n 29
o
2.3.3 Composici´n 30
o

6

´
INDICE GENERAL

iii

2.4

Funciones num´ricas 31
e
2.4.1 Calcular con enteros 31
2.4.2 Diferenciar num´ricamente 33
e
2.4.3 La ra´ cuadrada 34
ız
2.4.4 Ceros de una funci´n 35
o
2.4.5 Inverso de una funci´n 36
oEjercicios 38

3 Estructuras de datos 39
3.1 Listas 39
3.1.1 Estructura de una lista 39
3.1.2 Funciones sobre listas 41
3.1.3 Funciones de orden superior sobre listas 45
3.1.4 Ordenamiento de listas 47
3.2 Listas especiales 48
3.2.1 Cadenas 48
3.2.2 Caracteres 49
3.2.3 Funciones de cadenas y caracteres 50
3.2.4 Listas infinitas 52
3.2.5 Evaluaci´n perezosa 52
o
3.2.6 Funciones sobrelistas infinitas 53
3.3 Tuplas 56
3.3.1 Uso de tuplas 56
3.3.2 Definiciones de tipos 58
3.3.3 N´meros racionales 59
u
3.3.4 Listas y tuplas 60
3.3.5 Tuplas y currificaci´n 61
o
´
3.4 Arboles 61
3.4.1 Definiciones de datos 61
´
3.4.2 Arboles de b´squeda 64
u
3.4.3 Usos especiales de definiciones de datos 66
Ejercicios 68
4 Algoritmos sobre listas 75
4.1 Funciones combinatorias 75
4.1.1Segmentos y sublistas 75
4.1.2 Permutaciones y combinaciones
4.1.3 La notaci´n @ 79
o
Ejercicios 80

77

A Literatura relacionada con la Programaci´n Funcional
o

81

1

Cap´
ıtulo 1

Programaci´n Funcional
o
1.1
1.1.1

Lenguajes funcionales
Funciones

Los primeros ordenadores se construyeron en los a˜os cuarenta. Los primer´
n
ısimos modelos fueron ‘programados’ congrandes rel´s. Pronto se almacenaron los programas en la memoria del ordenador, haciendo
e
que los primeros lenguajes de programaci´n hicieran su entrada.
o
En aquel tiempo el uso de un ordenador era muy costoso y era l´gico que el lenguaje de programaci´n
o
o
guardara mucha relaci´n con la arquitectura del ordenador. Un ordenador consta de una unidad de control
o
y una memoria. Por eso un...