PDF de programación - Programación Funcional

Programación Funcional

2

Tabla de Contenidos

0.1. Evolución y Conceptos básicos
. . . . . . . . . . . . . . . . . . .
0.2. Definición de funciones . . . . . . . . . . . . . . . . . . . . . . . .
0.3. Sistema de Tipos . . . . . . . . . . . . . . . . . . . . . . . . . . .
0.3.1. Tipos Predefinidos primitivos . . . . . . . . . . . . . . . .
0.3.2. Tpos definidos por enumeración . . . . . . . . . . . . . . .
0.3.3. Tipos mediante Producto cartesiano . . . . . . . . . . . .
0.3.4. Combinación de productos y enumeraciones . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
0.3.5. Registros
. . . . . . . . . . . . . . . . . . . .
0.3.6. Tipos parametrizados
0.3.7. Tipos recursivos
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
0.3.8. Tipos recursivos parametrizados
0.4. Técnicas de programación Recursiva . . . . . . . . . . . . . . . .
0.4.1. Aplicar una función a cada elemento . . . . . . . . . . . .
0.4.2. Recorrer y transformar una estructura en un valor . . . .
0.4.3. Combinar dos estructuras . . . . . . . . . . . . . . . . . .
0.4.4. Listas intensionales . . . . . . . . . . . . . . . . . . . . . .
0.4.5. Otras posibilidades de recorrer y transformar una lista en
un valor . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0.4.6. Recorrer y transformar una estructura generando resulta-
. . . . . . . . . . . . . . . . . . . . . . . . .
0.4.7. Generar una estructura . . . . . . . . . . . . . . . . . . .
0.4.8. Otras estructuras recursivas . . . . . . . . . . . . . . . . .
0.4.9. Combinadores recursivos básicos
. . . . . . . . . . . . . .
0.5. Modelos de Evaluación . . . . . . . . . . . . . . . . . . . . . . . .
0.5.1. Evaluación impaciente vs. perezosa . . . . . . . . . . . . .
0.5.2. Programación con estructuras infinitas . . . . . . . . . . .
0.6. Entrada/Salida . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0.7. Clases de tipos
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
0.8. Técnicas de demostración . . . . . . . . . . . . . . . . . . . . . .
0.9. Programación a gran escala . . . . . . . . . . . . . . . . . . . . .
0.9.1. Sistema de Módulos
. . . . . . . . . . . . . . . . . . . . .
0.9.2. Tipos abstractos de datos . . . . . . . . . . . . . . . . . .

dos parciales

4
4
7
8
8
9
10
11
12
12
14
15
15
15
18
18

18

20
20
21
22
22
22
24
24
25
25
25
25
25

3

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

4

TABLA DE CONTENIDOS

0.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)

0.2. Definición de funciones

Los lenguajes funcionales utilizan un modelo computacional simple similar

al de una calculadora.

Definición 0.1 (Función) Una función entre dos conjuntos A y B es una re-
gla 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.

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)
> f t = \( x , y ) → 2 ∗ x + y
?− f t

( 3 , 4 ) 1 0

0.2. DEFINICI ÓN DE FUNCIONES

5

Mediante curryficación.

• Definición 0.2 (currificación) La currificación (currying) consis-
te en simular funciones de varios argumentos mediante funciones de
orden superior de un argumento

Ejemplo 3 (fc) La función fc toma un entero a y devuelve una fun-
ción que cuando toma un entero b devuelve 2∗a+b

> f c :: Int → ( Int → Int )
> f c = \ a → (\ b → 2 ∗ a + b )
?− f c 3 4 1 0

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 ’
> fc ’ x y = 2 ∗ x + y

:: Int → Int → Int

Las definiciones mediante currificación son muy habituales en Haske-
ll ya que, además de evitar paréntesis innecesarios, facilitan la apli-
cación parcial de funciones. De esa forma, la expresión fc 3 tiene
significado por sí misma.
?− r e a p l i c a ( f c 3 ) 4 1 6

Nota: En Haskell, una expresión del tipo (+2) se denomina una sección y equi-
vale 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 com-
posición, aunque está predefinida, podría definirse en Haskell como:

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 211

6

TABLA DE CONTENIDOS

Nota: 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.

> f a c t 0 = 1
> f a c t n = n ∗ f a c t
?− f a c t 5120

( n − 1)

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)
> s i g n o x | x > 0
= 1
| x == 0
= 0
>
| otherwise = −1
>

Nota: 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

0.3. SISTEMA DE TIPOS

7

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

> cuboS1 x = l e t
>
>

in cubo s i g

s i g = x + 1
cubo x = x ∗ x ∗ x

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

Ejemplo 12 (cuboS2) cuboS2 equivale a cuboS

> cuboS2 x = cubo s i g
>
>

where s i g = x + 1

cubo x = x ∗ x ∗ x

0.3. Sistema de Tipos

El universo de posibles valores que puede tomar una expresión se divide en

tipos

Definición 0.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 0.4 (Sistema de Inferencia de Tipos) Un sistema de inferen-
cia 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
comprueba que los tipos declarados encajan con los tipos inferidos por el sistema.

Ejemplo 13 (eligeSaludo)
> e l i g e S a l u d o x = i f x then ” Hola ,
>

e l s e ”Buenas

t i o ”

t a r d e s ”

8

TABLA DE CONTENIDOS

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

sistema infiere que tiene el tipo

> e l i g e S a l u d o :: Bool → String

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

0.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 ()

0.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 E s t a c i o n = Primavera | Otonio | Verano |

| Frio | Templado

= Calor

I n v i e r n o

Las definiciones de funciones sobre tipos enumerados pueden realizarse me-

diante encaje de patrones

:: E s t a c i o n → Temp

Ejemplo 15 (tempNormal)
> tempNormal
> tempNormal
> tempNormal
> tempNormal

Verano
I n v i e r n o = Frio

= Calor

= Templado

Es posible considerar que los tipos predefinidos primitivos han sido definidos

originalmente por enumeración.

0.3. SISTEMA DE TIPOS

9

data Bool = True | False
|
|
data Char = ’ a ’
data Int = − 3 2 7 6 7 | − 3 2 7 6 6 |
. . .

’ c ’

|

’ b ’

. . .
. . .

| − 1 | 0 | 1 |

. . . 3 2 7 6 7

0.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 E s t a c i o n Temp

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

Nota: ET es un constructor