PDF de programación - Parte II: Programación Funcional - Técnicas Básicas de la Programación funcional (usando Haskell)

Parte II: Programación Funcional

Técnicas Básicas de la Programación funcional (usando Haskell)

P. Julián-Iranzo

Universidad de Castilla-La Mancha

Programación Declarativa

versión Abril 2014

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

1 / 71

Índice

1 Objetivo

2 Concepto matemático de función

3 Funciones y programación funcional

4 Tipos

5 Definiciones

6 Definiciones recursivas, principio de inducción y propiedades de

programas

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

2 / 71

Índice

1 Objetivo

2 Concepto matemático de función

3 Funciones y programación funcional

4 Tipos

5 Definiciones

6 Definiciones recursivas, principio de inducción y propiedades de

programas

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

3 / 71

Objetivo

Introducir un nuevo paradigma de programación, la Programación
Funcional, presentando sus principales características y
mecanismos operacionales.
En particular, introducir el lenguaje Haskell, un lenguaje con
semántica no-estrícta que constituye un estándar del área.

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

4 / 71

Índice

1 Objetivo

2 Concepto matemático de función

3 Funciones y programación funcional

4 Tipos

5 Definiciones

6 Definiciones recursivas, principio de inducción y propiedades de

programas

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

5 / 71

Definición de función

Dados dos conjuntos D y E , una relación R ✓ D ⇥ E , es un subconjunto
de pares R = {(d, e) | d 2 D ^ e 2 E}: Si (d, e) 2 R escribimos d R e.
Definition (Función parcial)
Dados dos conjuntos D (dominio) y E (codominio o rango), una función
parcial f de D en E es una relación f ✓ D ⇥ E que verifica:

d f e ^ d f e0 ) e = e0

Entonces escribimos f : D ! E en vez de f ✓ D ⇥ E y f (d) = e en vez de
d f e.

En otras palabras: a cada elemento del dominio le corresponde un único
elemento del codominio. Si f (d) = e, decimos que e es la imagen de d
por f .

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

6 / 71

Definición de función

Definition (Función total)
Una función parcial f : D ! E es una función total si verifica la siguiente
propiedad:

8d 2 D. 9e 2 E . f (d) = e

Por tanto, una función total f : D ! E es una función parcial donde todo
elemento del dominio D tiene una imagen en E (por f ).

Example
La función sign : Int !{ neg, cero, pos} que asigna a un número entero su
signo (representado por neg, cero o pos) es una función total (todo
número entero tiene signo negativo, positivo o es cero).

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

7 / 71

Definición de función

A veces se representan las funciones como ‘cajas negras’ con una
entrada de datos (un elemento del dominio) y una salida de datos (el
elemento correspondiente del codominio).
Funciones multiargumento: f : D1 ⇥···⇥ Dk ! E .
Se pueden entender directamente como funciones f : D ! E de un
único argumento si escogemos D = D1 ⇥···⇥ Dk.
Una constante c puede entenderse como una función fc : !{ c} cuyo
dominio es el conjunto vacío y cuyo codominio es el conjunto unitario
que contiene el valor asociado a la constante.
Composición de funciones: Dadas dos funciones f : D ! E y
g : E ! F , la composición g f de ambas es una función
(g f ) : D ! F definida como (g f )(d) = g (f (d)).

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

8 / 71

Descripción de una función

Podemos distinguir dos formas básicas de describir una función f : D ! E :
Por extensión (o extensionalmente): dando el grafo de la función. Por
ejemplo, la función sign vendría descrita por el siguiente conjunto
(infinito) de pares:

{. . . , (2, neg), (1, neg), (0, cero), (1, pos), (2, pos), . . .}

Por comprensión (o intensionalmente): Indicando una regla que nos
permita establecer las asociaciones deseadas entre los elementos del
dominio y del codominio. Por ejemplo, la función anterior puede darse
como sigue:

sign(x) =8<:

neg
cero
pos

si x < 0
si x = 0
si x > 0

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

9 / 71

Descripción de una función

Ambas formas de definir una función son complementarias en el sentido de
que cada una de ellas sugiere distintos aspectos computacionales.

La definición intensional permite poner de manifiesto los aspectos
dinámicos o computacionales de la descripción de las funciones al
requerir que la función sea obtenida a partir de otras funciones
conocidas. Por tanto, de forma implícita, las definiciones intensionales
exigen utilizar algún tipo de proceso de cómputo para poder describir
una función.
La definición extensional centra la atención en los aspectos
estáticos o declarativos de la función, es decir en las asociaciones que
ésta establece entre los elementos del dominio y el codominio. Esto es
útil para discutir sobre la semántica de las funciones definidas
mediante reglas aparentemente distintas.

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

10 / 71

Descripción de una función

Example
Por ejemplo, las funciones doble : Int ! Int y doble0 : Int ! Int dadas por:

doble(x) = x + x

y

doble0(x) = 2 ⇤ x

tienen definiciones intensionales distintas. No obstante, los grafos de
ambas funciones coinciden:

{. . . , (2,4), (1,2), (0, 0), (1, 2), (2, 4), . . .}

Esto muestra que ambas funciones son idénticas (de acuerdo con el
principio de extensionalidad).

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

11 / 71

Propiedades de las funciones

Determinismo: A cada elemento del dominio de una función le
corresponde un único elemento del codominio.
Dependencia de los argumentos: El valor de una función aplicada
sobre sus argumentos viene determinado exclusivamente por éstos.
Transparencia referencial: El resultado de la evaluación de una
función es independiente del momento y lugar desde el que se la
referencia. Cada expresión designa un único valor independientemente
del modo en que se evalúa.
Extensionalidad: Dos funciones f : D ! E y g : D ! E son iguales si
para cada elemento del dominio las imagenes de ambas son iguales:
(8d 2 D. f (d) = g (d)) ) f = g

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

12 / 71

Funciones y lenguajes de programación
convencionales (opacidad referencial)

Example

boolean;

program example(output);
var flag:
function f(x:Integer): integer;
begin
IF flag THEN f:=x ELSE else f:=2*x;
flag:=not flag;
end
begin
flag:= true;
writeln(f(1)+f(2));
writeln(f(2)+f(1));
end.

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

13 / 71

Aplicación de una función

Constituye el principio dinámico básico derivado del concepto de
función.
Una función f aplicada sobre un argumento o parámetro real d
constituye una expresión f (d) cuya evaluaciónˆEes el valor e del
codominio de la función que es asignado por f al elemento d.
La composición de funciones junto con la aplicación constituye el
principio básico para definir las expresiones susceptibles de representar
cómputos.

Observación
Distinguir entre parámero formal (usado en la definición de la función) y
parámero real o argumento.

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

14 / 71

Índice

1 Objetivo

2 Concepto matemático de función

3 Funciones y programación funcional

4 Tipos

5 Definiciones

6 Definiciones recursivas, principio de inducción y propiedades de

programas

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

15 / 71

Funciones y programación funcional

Del concepto de función, surge la idea de disponer de un lenguaje de
programación que permita la definición de funciones y la especificación de
expresiones cuya evaluación puede entenderse como la ejecución del
programa.

Componente estático: El perfil de una función f : D ! E , sugiere la
necesidad de describir los dominios de definición de las funciones y las
funciones en sí mismas:

Dominios
D ! E

z }| {

Función

f :|{z}

I La descripción de dominios nos lleva a la idea de tipo.
I La descripción de funciones a la idea de definición de función.

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

16 / 71

Funciones y programación funcional

Del concepto de función, surge la idea de disponer de un lenguaje de
programación que permita la definición de funciones y la especificación de
expresiones cuya evaluación puede entenderse como la ejecución del
programa.

Componente dinámico: La noción de aplicación de una función a sus
argumentos sugiere que el componente dinámico del paradigma debe
dar cuenta de cómo evaluar expresiones, de acuerdo con la
descripción dada para las funciones involucradas.

Observación
Seguiremos la sintaxis de Haskell en los ejemplos: La aplicación de una
función f sobre sus argumentos e1,...,ek se denota

en lugar de f(e1,...,ek ).

f e1 ··· ek

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

17 / 71

Índice

1 Objetivo

2 Concepto matemático de función

3 Funciones y programación funcional

4 Tipos

5 Definiciones

6 Definiciones recursivas, principio de inducción y propiedades de

programas

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

18 / 71

Motivación e introducción

El uso de tipos en programación obedece a dos motivaciones
fundamentales:

Evitar o detectar errores de programación.
Ayudar a definir estructuras de datos.

En un lenguaje de programación tipificado (typed), todos los valores y
expresiones manejadas tienen un tipo.
=) Restricción en la variedad de expresiones que podemos considerar en

nuestros programas.

Sólo están permitidas las expresiones bien tipificadas.

Observación
En Haskell, el comando :type infiere y muestra el tipo de una expresión.

P. Julián (UCLM)

PROGRAMACI ÓN DECLARATIVA.

ver. Abril 2014

19 / 71

Motivación e introducción

El uso de tipos en un lenguaje