PDF de programación - Programación Funcional

Programación Funcional

Jeroen Fokker

1996

Universidad de Utrecht
Departamento de Informática

Traducci’on: Programa MEMI

Universidad Mayor de San Simón
Hielko R. Ophoff & Bernardo Sánchez J.

Revisión: Universidad Carlos III de Madrid

Carlos Delgado Kloos & Natividad Martínez Madrid

Programación Funcional

cCopyright 1992–1996 Departamento de Informática, Universidad de Utrecht
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
Segunda edición: Agosto 1995
Segunda edición revisada: Marzo 1996

ii

Índice General

1 Programación Funcional

1.1 Lenguajes funcionales
1
1

1.1.1 Funciones
1.1.2 Lenguajes

1.2 El intérprete de Gofer 2

1

1

1.2.1 Calcular expresiones
1.2.2 Definir funciones
4
1.2.3 Comandos del intérprete

2

5

1.3 Funciones estándar 6

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
1.3.4 Funciones booleanas
9
1.3.5 Funciones sobre listas
1.3.6 Funciones de funciones

10

11

8

6

1.4 Definición de funciones

11

1.4.1 Definición por combinación 11
1.4.2 Definición por distinción de casos
12
1.4.3 Definición por análisis de patrones 13
1.4.4 Definición por recursión o inducción 14
1.4.5

Indentación y comentarios

15

1.5 Tipado 16

16

1.5.1 Clases de errores
1.5.2 Expresiones de tipo 18
1.5.3 Polimorfismo
1.5.4 Funciones con más de un parámetro 20
1.5.5

Sobrecarga 20

19

Ejercicios 21

2 Números y funciones

23

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

2.2 Currificación 25

Instanciar parcialmente

2.2.1
2.2.2 Paréntesis
2.2.3

26

Secciones de operadores
27

2.3 Funciones como parámetros
2.3.1 Funciones sobre listas
2.3.2
2.3.3 Composición 30

Iteración 29

27

25

27

ÍNDICE GENERAL

iii

2.4 Funciones numéricas

31

31

2.4.1 Calcular con enteros
2.4.2 Diferenciar numéricamente
2.4.3 La raíz cuadrada 34
2.4.4 Ceros de una función 35
2.4.5
Ejercicios

Inverso de una función 36
38

33

3 Estructuras de datos

39

3.1 Listas

39

3.2 Listas especiales

3.1.1 Estructura de una lista
3.1.2 Funciones sobre listas
3.1.3 Funciones de orden superior sobre listas
3.1.4 Ordenamiento de listas

41

39

47

48
3.2.1 Cadenas 48
3.2.2 Caracteres
3.2.3 Funciones de cadenas y caracteres
3.2.4 Listas infinitas 52
3.2.5 Evaluación perezosa 52
3.2.6 Funciones sobre listas infinitas

49

53

50

3.3 Tuplas 56

59

58

3.3.1 Uso de tuplas 56
3.3.2 Definiciones de tipos
3.3.3 Números racionales
3.3.4 Listas y tuplas
60
3.3.5 Tuplas y currificación 61
Árboles
3.4.1 Definiciones de datos 61
Árboles de búsqueda 64
3.4.2
3.4.3 Usos especiales de definiciones de datos

61

3.4

Ejercicios 68

45

66

4 Algoritmos sobre listas

75

4.1 Funciones combinatorias

75
Segmentos y sublistas

4.1.1
4.1.2 Permutaciones y combinaciones
4.1.3 La notación @ 79

75

77

Ejercicios 80

A Literatura relacionada con la Programación Funcional

81

1

Capítulo 1

Programación Funcional

1.1 Lenguajes funcionales

1.1.1 Funciones

Los primeros ordenadores se construyeron en los años cuarenta. Los primerísimos modelos fueron ‘progra-
mados’ con grandes relés. Pronto se almacenaron los programas en la memoria del ordenador, haciendo
que los primeros lenguajes de programación hicieran su entrada.
En aquel tiempo el uso de un ordenador era muy costoso y era lógico que el lenguaje de programación
guardara mucha relación con la arquitectura del ordenador. Un ordenador consta de una unidad de control
y una memoria. Por eso un programa consistía en instrucciones para cambiar el contenido de la memoria. La
unidad de control se encargaba de ejecutarlas. De esta manera se creó el estilo de programación imperativa.
Los lenguajes de programación imperativa como Pascal y C se caracterizan por la existencia de asignaciones
ejecutadas consecutivamente.
Antes de la existencia de los ordenadores se inventaron métodos para resolver problemas. Por tanto, no
existía la necesidad de hablar en términos de una memoria que cambie por instrucciones en un programa.
En la matemática de los últimos cuatrocientos años son muy importantes las funciones. Éstas establecen
la relación entre los parámetros (la ‘entrada’) y el resultado (la ‘salida’) de procesos definidos.
Con cada computación, el resultado depende de una u otra forma de los parámetros. Por esa razón, una
función es una buena manera de especificar una computación. Ésta es la base del estilo de programación
funcional. Un ‘programa’ consiste en la definición de una o más funciones. Para la ejecución de un
programa, se dan parámetros a una función y el ordenador tiene que calcular el resultado. Con este tipo
de computación existe libertad en la manera de ejecución. ¿Por qué tendría que describirse en qué orden
deben ejecutarse las computaciones parciales?
Con el tiempo, al bajar los precios de los ordenadores y al subir los precios de los programadores, llega a ser
más importante describir las computaciones en un lenguaje que esté más cerca del ‘mundo del hombre’, que
cerca del ordenador. Los lenguajes funcionales se unen a la tradición matemática y no están muy influidos
por la arquitectura concreta del ordenador.

1.1.2 Lenguajes

La base teórica de la programación imperativa fue dada (en Inglaterra) por Alan Turing en los años treinta.
También la teoría de funciones como modelo de computación proviene de los años veinte y treinta. Los
fundadores son, entre otros, M. Sch¨onfinkel (en Alemania y Rusia), Haskell Curry (en Inglaterra) y Alonzo
Church (en los Estados Unidos).
Fue en el comienzo de los años cincuenta cuando a alguien se le ocurrió usar esta teoría efectivamente,
como base de un lenguaje de programación. El lenguaje Lisp de John McCarthy fue el primer lenguaje de

2

Programación Funcional

programación funcional y fue el único por muchos años. Aunque todavía se usa Lisp, no es un lenguaje que
reuna las exigencias. Debido a la creciente complejidad de los programas de ordenador, se hizo necesaria
una mayor verificación del programa por parte de el ordenador. Por ello el tipado adquirió una gran
importancia. Por eso no es de extrañar que en los años ochenta se crearan un gran número de lenguajes
funcionales tipados. Algunos ejemplos son ML, Scheme (una adaptación de Lisp), Hope y Miranda.
A la larga, cada investigador se dedicó a desarrollar su propio lenguaje. Para detener este crecimien-
to incontrolado, un grupo de investigadores notables concibió un lenguaje que incluía todas las mejores
cualidades de los diferentes lenguajes. Este lenguaje se llama Haskell. Las primeras implementaciones de
Haskell fueron hechas a comienzos de los años noventa. Este lenguaje es bastante ambicioso y de difícil
implementación. El lenguaje Gofer es un lenguaje como Haskell, pero un poco más simple. Se usa para in-
vestigaciones teóricas y para metas educativas. Por su gran disponibilidad gana popularidad rápidamente.
La pregunta es si Gofer sobrevivirá. Esto no importa mucho, el estudio de Gofer es útil porque tiene una
relación fuerte con Haskell, que está aceptado por mucha gente en el área de la informática.
Los lenguajes ML y Scheme tienen también muchos seguidores. Estos lenguajes han hecho algunas con-
cesiones en la dirección de los lenguajes imperativos. Son de menos utilidad para mostrar lo que es un
lenguaje funcional propio. Miranda es un lenguaje funcional propio, pero es difícil obtenerlo.
En este texto se utiliza el lenguaje Gofer. En este lenguaje se usan muchos conceptos de una manera
consecuente, lo que hace que pueda ser aprendido fácilmente. Quien conozca Gofer, tendrá pocos problemas
en comprender otros lenguajes funcionales.

1.2 El intérprete de Gofer

1.2.1 Calcular expresiones

En un lenguaje funcional se pueden definir funciones. Estas funciones se usan en una expresión cuyo valor
tiene que ser calculado. Para calcular el valor de una expresión se necesita un programa que entienda las
definiciones de las funciones. Tal programa se llama intérprete.
Para el lenguaje Gofer que se usa en este texto existe un intérprete. Para iniciar el intérprete se teclea el
nombre del programa, gofer. En la pantalla aparece lo siguiente:

%gofer
Gofer Version 2.21

Copyright (c) Mark P Jones 1991

Reading script file "/usr/local/lib/gofer/prelude":
Parsing....................
Dependency analysis........
Type checking..............
Compiling..................

En el fichero prelude (que en este ejemplo está en el directorio /usr/local/lib/gofer) están las defini-
ciones de las funciones estándar. Lo primero que hace el intérprete de Gofer es analizar estas funciones
estándar.
‘Prelude’ significa ‘preludio’: este archivo se examina antes de que se puedan definir nuevas
funciones. En el caso de este ejemplo no hay nuevas funciones, por eso el intérprete indica con

Gofer session for:
/usr/local/lib/gofer/prelude

que se pueden usar solamente las definiciones que están en el preludio. Finalmente, el intérprete comunica
que se puede teclear :? para obtener algunas instrucciones para el uso:

Type :? for help
?

1.2 El intérprete de Gofer

3

El signo de interrogación indica que el intérprete está listo para calcular el valor de una expresión. En el
prelude están definidas, entre otras, las funciones aritméticas. Por eso, se puede usar el intérprete como
calculadora.

? 5+2*3
11
(5 reductions, 9 cells)
?

El intérprete calcula el valor de la expresión (el operador * indica multiplicación). Después de decir cuál
es el resultado, el intérprete indica lo que fue necesario para el cálculo: ‘5 reductions’ (una medida para el
tiempo utilizado) y ‘9 cells’ (una