PDF de programación - Programación Funcional

Programación Funcional

Jose Emilio Labra Gayo

Índice General

1 Evolución y Conceptos básicos

2 Definición de funciones

3 Sistema de Tipos

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

3

3

7
8
8
9
10
12
13
13
15

4 Técnicas de programación Recursiva

16
16
4.1 Aplicar una función a cada elemento . . . . . . . . . . . . . . . .
17
4.2 Recorrer y transformar una estructura en un valor
. . . . . . . .
19
4.3 Combinar dos estructuras . . . . . . . . . . . . . . . . . . . . . .
20
4.4 Listas intensionales . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Otras posibilidades de recorrer y transformar una lista en un valor 20
4.6 Recorrer y transformar una estructura generando resultados par-
ciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7 Generar una estructura . . . . . . . . . . . . . . . . . . . . . . .
4.8 Otras estructuras recursivas . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
4.9 Combinadores recursivos básicos

22
22
23
25

5 Modelos de Evaluación

5.1 Evaluación impaciente vs. perezosa . . . . . . . . . . . . . . . . .
5.2 Programación con estructuras infinitas . . . . . . . . . . . . . . .

6 Entrada/Salida

7 Clases de tipos

8 Técnicas de demostración

1

25
25
27

28

28

28

ÍNDICE GENERAL

9 Programación a gran escala

9.1 Sistema de Módulos
. . . . . . . . . . . . . . . . . . . . . . . . .
9.2 Tipos abstractos de datos . . . . . . . . . . . . . . . . . . . . . .

2

28
28
28

kFalta por
hacer: Falta
por desarrollar
esta sección
con más
detallek

1 EVOLUCI ÓN Y CONCEPTOS B ÁSICOS

3

1 Evolución y Conceptos básicos

• Bases teóricas: cálculo lambda de Church
• LISP, Funciones de orden superior
• ISWIM, notación infija
• FP, combinadores
• ML, polimorfismo paramétrico, chequeo estático de tipos, inferencia de

tipos

• Hope, encaje de patrones
• Miranda, Evaluación perezosa
• Haskell, sobrecarga (clases de tipos), Entrada/Salida (mónadas)

2 Definición de funciones

Los lenguajes funcionales utilizan un modelo computacional simple similar al de
una calculadora.

Definición 1 (Función) Una función entre dos conjuntos A y B es una regla
que permite asociar a cada elemento x perteneciente a A, un elemento y perte-
neciente a B

Existen diversos métodos de definición de funciones.
• La notación lambda

Ejemplo 1 (suma2)

> suma3 = \x -> x + 3

En Haskell, todas las funciones tienen un único argumento. Para definir
funciones de más de un argumento se pueden utilizar dos posibilidades.

– Mediante tuplas
Ejemplo 2 (ft)

> ft = \(x,y) -> 2 * x + y

2 DEFINICI ÓN DE FUNCIONES

4

?-ft (3,4)
10

Mediante curryficación.

– Definición 2 (currificación) La currificación (currying) consiste
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
función que cuando toma un entero y devuelve 2*x+y

> 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 paréntesis de la declaración anterior y La nota-
ción lambda puede simplificarse mediante encaje de patrones. Dicha
definición podría reescribirse como:
Ejemplo 4 (fc’)

> fc’ :: Int -> Int -> Int
> fc’ x y = 2 * x + y

Las definiciones mediante currificación son muy habituales en Haskell
ya que, además de evitar paréntesis innecesarios, facilitan la aplica-
ción parcial de funciones. De esa forma, la expresión fc 3 tiene
significado por sí misma.

?-reaplica (fc 3) 4
16
En Haskell, una expresión del tipo (+2) se denomina una sección y
equivale a la aplicación parcial de la función correspondiente, en este
caso (+)

• Mediante composición de funciones. La composición de funciones es un
recurso habitual en la definición de procesos iterativos. La función de
composición, aunque está predefinida, podría definirse en Haskell como:

2 DEFINICI ÓN DE FUNCIONES

5

Ejemplo 5 (comp)

> comp :: (b -> c) -> (a -> b) -> a -> c
> comp f g = \x -> f ( g x)

Ejemplo 6 (fcm)

> fcm = comp (+3) (*4)

?-fcm 2
11

La función composición está predefinida como el operador (.).

Ejemplo 7 (fcm’) La función fcm’ equivale a la función fcm

> fcm’ = (+3) . (*4)

Encaje de patrones. Las definiciones de funciones pueden realizarse me-
diante una serie de ecuaciones. En cada ecuación pueden incluirse varios
patrones que el sistema intenta encajar según el orden en que fueron es-
critos. En cuanto un patrón encaje, se devuelve el valor correspondiente.

• Ejemplo 8 (fact) La función fact devuelve el factorial de un número.

> fact 0 = 1
> fact n = n * fact (n - 1)

?-fact 5
120

2 DEFINICI ÓN DE FUNCIONES

6

Ecuaciones con guardas. En las definiciones pueden incluirse unas condi-
ciones, denominadas . El sistema evalúa las guardas de cada ecuación. Si
encuentra una guarda cuyo valor sea True, devuelve el resultado corres-
pondiente.

• Ejemplo 9 (signo)

> signo x | x > 0
>
>

| x == 0
| otherwise = -1

= 0

= 1

La palabra reservada otherwise equivale a True

• Declaraciones locales. En la definición de funciones es posible utilizar de-
claraciones locales que facilitan la legibilidad y la reusabilidad del código.

Ejemplo 10 (cuboS) La función cuboS calcula el cubo del siguiente de
un número

> cuboS x = (x + 1) * (x + 1) * (x + 1)

Las declaraciones locales pueden introducirse mediante la combinación
let x = ELocal in Expr

Ejemplo 11 (cuboS1) cuboS1 equivale a cuboS pero utiliza declaracio-
nes locales.

> cuboS1 x = let sig = x + 1
>
cubo x = x * x * x
>

in cubo sig

Otra posibilidad para definir declaraciones locales es la utilización de la
palabra where

3 SISTEMA DE TIPOS

7

Ejemplo 12 (cuboS2) cuboS2 equivale a cuboS

> cuboS2 x = cubo sig
>
>

where sig = x + 1
cubo x = x * x * x

3 Sistema de Tipos

El universo de posibles valores que puede tomar una expresión se divide en tipos
Definición 3 (Tipo) Un tipo es un conjunto de valores que puede tomar una
expresión.

En Haskell, un valor pertenece a un único tipo, que es reconocido y compro-
bado por el sistema sin necesidad de ejecutar el programa. Se realiza, por tanto,
una comprobación de tipos en tiempo de compilación. Las principales ventajas
son:

• Seguridad, se impide la ejecución de programas que podrían producir erro-

res de tipo.

• Eficiencia, no es necesario realizar comprobaciones de tipo en tiempo de

ejecución.

Definición 4 (Sistema de Inferencia de Tipos) Un sistema de inferencia
de tipos permite inferir los tipos de las expresiones sin obligar al programador a
su declaración explícita. En caso de que el programador los haya declarado, se
comtest que los tipos declarados encajan con los tipos inferidos por el sistema.

Ejemplo 13 (eligeSaludo)

> eligeSaludo x = if x then "Hola, tio"
>

else "Buenas tardes"

No es necesario declarar el tipo de la función eligeSaludo. No obstante, el

sistema infiere que tiene el tipo

> eligeSaludo :: Bool -> String

3 SISTEMA DE TIPOS

8

La declaración de tipos puede verse como una especificación de lo que el pro-
gramador pretende realizar. Dicha especificación puede comprobarse de forma
automática sin necesidad de ejecutar el programa.

3.1 Tipos Predefinidos primitivos
El sistema Haskell cuenta con una serie de tipos primitivos predefinidos. Los
más importantes son:

• Char indica el conjunto de caracteres con el formato ’a’, ’A’, ’1’, ’\n’, ...
• Bool indica valores booleanos. Pueden ser True o False
• Int indica enteros con límite. Por ejemplo 123, -456, ...
• Integer indica enteros sin límite. Por ejemplo 123123123123, -123456789, ...
• Float indica números en coma flotante. Por ejemplo 12.45, 12e3, ...
• () indica el tipo nulo que solamente incluye el valor ()

3.2 Tpos definidos por enumeración
El usuario puede definir nuevos tipos de datos mediante la enumeración de sus
valores

Ejemplo 14 (Temp)

> data Temp
> data Estacion = Primavera | Otonio | Verano | Invierno

= Calor | Frio | Templado

Las definiciones de funciones sobre tipos enumerados pueden realizarse me-

diante encaje de patrones

Ejemplo 15 (tempNormal)

> tempNormal :: Estacion -> Temp
> tempNormal
= Calor
> tempNormal
> tempNormal

Verano
Invierno = Frio
_

= Templado

Es posible considerar que los tipos predefinidos primitivos han sido definidos

originalmente por enumeración.

3 SISTEMA DE TIPOS

9

data Bool = True | False
data Char = ’a’ | ’b’ | ’c’ | ...
data Int = -32767 | -32766 | ... | -1 | 0 | 1 | ... 32767
...

3.3 Tipos mediante Producto cartesiano
En ocasiones se desea definir un tipo a partir del producto cartesiano de los
valores de otros tipos.

Ejemplo 16 (EstadoTemp) El estado de las temperaturas en una determi-
nada época del año puede definirse como el producto cartesiano de los tipos
Estacion y Temp

> data EstadoTemp = ET Estacion Temp

Un posible valor sería ET Verano Templado :: EstadoTemp

ET es un constructor de tipos que actúa como una función ET ::
Estacion
-> Temp -> EstadoTemp que permite obtener un EstadoTemp a partir de una
estación y una temperatura.

Las funciones sobre los tipos producto también pueden definirse mediante

encaje de patrones

Ejemplo 17 (estadoNormal)

> estadoNormal :: EstadoTemp -> Bool
> estadoNormal (ET Verano
> estadoNormal (ET Invierno Frio
> estadoNormal (ET _
> estadoNormal (ET _

) = True
) = True
Templado) = True
_

Calor

) = False

Ejemplo 18 (Números C