Programación

Programaci´n Funcional
o
Jose Emilio Labra Gayo

´
Indice General
1 Evoluci´n y Conceptos b´sicos
o
a

3

2 Definici´n de funciones
o

3

3 Sistema de Tipos
3.1 Tipos Predefinidos primitivos . . . . . . . .
3.2 Tpos definidos por enumeraci´n . . . . . . .
o
3.3 Tipos mediante Producto cartesiano . . . .
3.4 Combinaci´n de productos y enumeraciones
o
3.5 Registros . . . . . .. . . . . . . . . . . . .
3.6 Tipos parametrizados . . . . . . . . . . . .
3.7 Tipos recursivos . . . . . . . . . . . . . . .
3.8 Tipos recursivos parametrizados . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
..
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

4 T´cnicas de programaci´n Recursiva
e
o
4.1 Aplicar una funci´n a cada elemento . . . . . . . . . . . . . . . .
o
4.2 Recorrer y transformar una estructura en un valor . . . . . . . .
4.3 Combinar dos estructuras . . . . . . . . . . . . . . . . . . . . . .
4.4 Listas intensionales . . . . . . . . .. . . . . . . . . . . . . . . . .
4.5 Otras posibilidades de recorrer y transformar una lista en un valor
4.6 Recorrer y transformar una estructura generando resultados parciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7 Generar una estructura . . . . . . . . . . . . . . . . . . . . . . .
4.8 Otras estructuras recursivas . . . . . . . . . . . . . . . . . . . . .4.9 Combinadores recursivos b´sicos . . . . . . . . . . . . . . . . . .
a

7
8
8
9
10
12
13
13
15
16
16
17
19
20
20
22
22
23
25

5 Modelos de Evaluaci´n
o
25
5.1 Evaluaci´n impaciente vs. perezosa . . . . . . . . . . . . . . . . . 25
o
5.2 Programaci´n con estructuras infinitas . . . . . . . . . . . . . . . 27
o
6 Entrada/Salida

28

7 Clases de tipos

28

8T´cnicas de demostraci´n
e
o

28

1

´
INDICE GENERAL

2

9 Programaci´n a gran escala
o
28
9.1 Sistema de M´dulos . . . . . . . . . . . . . . . . . . . . . . . . . 28
o
9.2 Tipos abstractos de datos . . . . . . . . . . . . . . . . . . . . . . 28

1

1

´
´
EVOLUCION Y CONCEPTOS BASICOS

3

Evoluci´n y Conceptos b´sicos
o
a
• Bases te´ricas: c´lculo lambda de Churcho
a
• LISP, Funciones de orden superior
• ISWIM, notaci´n infija
o
• FP, combinadores
• ML, polimorfismo param´trico, chequeo est´tico de tipos, inferencia de
e
a
tipos
• Hope, encaje de patrones
• Miranda, Evaluaci´n perezosa
o
• Haskell, sobrecarga (clases de tipos), Entrada/Salida (m´nadas)
o

2

Definici´n de funciones
o

Los lenguajes funcionales utilizan un modelocomputacional simple similar al de
una calculadora.
Definici´n 1 (Funci´n) Una funci´n entre dos conjuntos A y B es una regla
o
o
o
que permite asociar a cada elemento x perteneciente a A, un elemento y perteneciente a B
Existen diversos m´todos de definici´n de funciones.
e
o
• La notaci´n lambda
o
Ejemplo 1 (suma2)
> suma3 = \x -> x + 3

En Haskell, todas las funciones tienen un unicoargumento. Para definir
´
funciones de m´s de un argumento se pueden utilizar dos posibilidades.
a
– Mediante tuplas
Ejemplo 2 (ft)
> ft = \(x,y) -> 2 * x + y

Falta por
hacer: Falta
por desarrollar
esta secci´n
o
con m´s
a
detalle

2

´
DEFINICION DE FUNCIONES

4

?-ft (3,4)
10
Mediante curryficaci´n.
o
– Definici´n 2 (currificaci´n) La currificaci´n (currying) consiste
o
oo
en simular funciones de varios argumentos mediante funciones de
orden superior de un argumento
Ejemplo 3 (fc) La funci´n fc toma un entero x y devuelve una
o
funci´n que cuando toma un entero y devuelve 2*x+y
o

> fc :: Int -> (Int -> Int)
> fc = \x -> (\y -> 2 * x + y)

?-fc 3 4
10
En realidad, la precedencia de las declaraciones de tipos en Haskell
hace innecesarios los...