PDF de programación - Capítulo 1. Programación Funcional

Capítulo 1. Programación Funcional

1

Programación funcional

Funciones

f : A → B
f (x)
→ . . .

Ejemplos: sucesor, sumaCuadrados (2 argumentos) y pi (constante)

sucesor : Z → Z
sucesor(x)

→ x + 1

sumaCuadrados : Z × Z → Z
sumaCuadrados(x, y)

→ x2 + y2

π :
π → 3.1415927 . . .

R

Evaluación de una función para ciertos valores de la variable:

sucesor(1) =⇒ 2 sumaCuadrados(2, 3) =⇒ 13

Capítulo 1. Programación Funcional

2

Prelude> [1..5]
[1, 2, 3, 4, 5] ::

[Integer ]

Prelude> sum [1..10]
55 :: Integer

El siguiente ejemplo muestra cómo se usan
funciones de más de un argumento:

Prelude> mod 10 3
1 :: Integer

Prelude> mod 10 (3 + 1)
2 :: Integer

Sesiones y declaraciones

• Programar = especificar los pasos para resolver
un problema.
• Solución a un problema = valor calculado a
partir de ciertos datos.
En programación funcional, ordenador = calcu-
ladora o evaluador

Existen un conjunto de funciones predefinidas

(Prelude)

Prelude> 1 + 2
3 :: Integer

Las líneas anteriores representan un diálogo con
el evaluador.
El siguiente ejemplo utiliza valores reales:

Prelude> cos pi
− 1.0 :: Double

Sólo se usan paréntesis cuando es necesario:

Prelude> cos (2 ∗ pi )
1.0 :: Double

Capítulo 1. Programación Funcional

3

• Haskell es un lenguaje fuertemente tipificado.

Proporciona un rico conjunto de elementos predefinidos.
Este conjunto es ampliable vía declaraciones o definiciones:

sucesor
sucesor x = x + 1

:: Integer → Integer – – declaración de tipo

– – cómo computar el valor de la función

Main> sucesor 3
4 :: Integer
Main> 10 ∗ sucesor 3
40 :: Integer

Las siguientes declaraciones muestra la definición de una función de dos argumentos:

sumaCuadrados
sumaCuadrados x y = x ∗ x + y ∗ y

:: Integer → Integer → Integer

Main> sumaCuadrados 2 3
13 :: Integer
Main> sumaCuadrados (2 + 2) 3
25 :: Integer

Los tipos de los distintos argumentos aparecen separados por el constructor de tipo →.

El último tipo es el del resultado.

Capítulo 1. Programación Funcional

4

Reducción de expresiones

La labor del evaluador consiste en:

mientras quede algún redex en la expresión

seleccionar un redex y
reducirlo

Una vez alcanzada la forma normal, el evaluador
muestra el resultado.

¿Qué ocurre si hay más de un redex?.

Por ejemplo cuadrado (cuadrado 3)

• El evaluador simplifica la expresión original to-
do lo posible y muestra el resultado.
• La simplificación se produce, en general, tras
varios pasos:

cuadrado
cuadrado x = x ∗ x

:: Integer → Integer

podemos calcular el valor de la expresión:

2 + cuadrado 3

=⇒ ! por la definición de cuadrado

2 + (3 ∗ 3)

=⇒ ! por el operador (∗)

2 + 9

=⇒ ! por el operador (+)

11

Cada paso es una reducción.
Un redex es cada parte de la expresión que
pueda reducirse.
Cuando una expresión no puede ser reducida
más se dice que está en forma normal.

Capítulo 1. Programación Funcional

5

=⇒ ! por la definición de (∗)

9 ∗ (cuadrado 3)

=⇒ ! por la definición de cuadrado

9 ∗ (3 ∗ 3)

=⇒ ! por el operador (∗)

9 ∗ 9

=⇒ ! por el operador (∗)

81

Para reducir la expresión e1 ∗ e2 hay que reducir
previamente e1 y e2. (∗ es estricto).

• Podemos reducir la expresión desde dentro ha-
cia fuera (primero los redexes internos):

cuadrado(cuadrado 3)

=⇒ ! por la definición de cuadrado

cuadrado(3 ∗ 3)

=⇒ ! por el operador (∗)

cuadrado 9

=⇒ ! por la definición de cuadrado

9 ∗ 9

=⇒ ! por el operador (∗)

81

Esta estrategia presenta algunos problemas.

• Una estrategia mejor consiste en reducir la ex-
presión desde fuera hacia dentro (primero los re-
dexes externos):

cuadrado x =⇒ x ∗ x

No es necesario evaluar previamente el argumen-
to para aplicar la definición de la función cuadrado.

cuadrado(cuadrado 3)

=⇒ ! por la definición de cuadrado

(cuadrado 3) ∗ (cuadrado 3)

=⇒ ! por la definición de cuadrado

(3 ∗ 3) ∗ (cuadrado 3)

Capítulo 1. Programación Funcional

6

cero infinito

=⇒ ! por definición de cero

0

∀ n :: Integer cero n =⇒ 0.
En particular, cero infinito =⇒ 0.

La estrategia utilizada para seleccionar el redex
es crucial.

Transparencia referencial

Sea cual sea la estrategia seguida en las reduccio-
nes, el resultado final (el valor 81) es el mismo:
Si aparecen varios redexes, podemos elegir
cualquiera.
Sin embargo, la reducción de un redex equivo-
cado puede que no conduzca a la forma normal
de una expresión:

infinito :: Integer
infinito = 1 + infinito
cero
cero x = 0

:: Integer → Integer

• Si en cada momento elegimos el redex más
interno:

cero infinito

=⇒ ! por definición de infinito

cero (1 + infinito)

=⇒ ! por definición de infinito

cero (1 + (1 + infinito))

=⇒ ! por definición de infinito

. . .

y la evaluación no terminaría nunca.

• Si en cada paso elegimos el redex más externo:

Capítulo 1. Programación Funcional

7

Problema aún mayor: puede no conducir a

la forma normal de la expresión. Por ejemplo:

cero infinito

• Orden de reducción normal

Consiste en seleccionar el redex más externo y

más a la izquierda.
Esta estrategia de reducción se conoce como
paso de parámetros por nombre (call by name).
A los evaluadores que utilizan el orden normal
se los llama no estrictos.
El paso por nombre es normalizante

Órdenes de reducción aplicativo y normal

orden de reducción = Estrategia que indica qué re-
dex hay que seleccionar en cada paso de la reduc-
ción.
Existen varios órdenes de reducción. Dos de los
más interesantes:
• Orden aplicativo
• orden normal.
• Orden aplicativo:

Seleccionar siempre el redex más interno y más

a la izquierda.
Esta estrategia de reducción es conocida como
paso de parámetros por valor (call by value).
A los evaluadores que utilizan este orden se
los llama estrictos o impacientes.
• Problemas del paso por valor
A veces, se efectúan reducciones que no son

necesarias:

cero (10 ∗ 4)

=⇒ ! por el operador (∗)

cero 40

=⇒ ! por definición de cero

0

Capítulo 1. Programación Funcional

8

Evaluación perezosa

• Con paso por nombre ciertas expresiones se
reducen varias veces.

En cuadrado (cuadrado 3) la expresión:
(3 ∗ 3)
es calculada 2 veces.

• Esto no ocurre en la reducción que usa paso
por valor
• La estrategia de paso de parámetros por ne-
cesidad (call by need), también conocida como
evaluación perezosa, soluciona este problema.
La evaluación perezosa consiste en utilizar pa-
so por nombre y recordar los valores de los argu-
mentos ya calculados para evitar recalcularlos:

cuadrado (cuadrado 3)

=⇒ ! por la definición de cuadrado

a ∗ a donde a = cuadrado 3

=⇒ ! por la definición de cuadrado

cuadrado x

=⇒

*

-

x



cuadrado

cuadrado

3

=⇒

*

-

cuadrado 3

a ∗ a donde a = b ∗ b donde b = 3

81

⇐=

=⇒ ! por el operador (∗)

a ∗ a donde a = 9

=⇒ ! por el operador (∗)

81

*

9-



⇐=

-

⇓

*

*



3-