Tema 1: Introducción a la programación funcional

Índice

1. Funciones
2. Programación funcional y programación imperativa
3. Rasgos característicos de Haskell
4. Antecedentes históricos
5. Presentación de Haskell
- 5.1. Ejemplo de recursión sobre listas
- 5.2. Ejemplo con listas de comprensión
6. Material complementario
7. Bibliografía

import Test.QuickCheck

1. Funciones

1.1. Funciones en Haskell

En Haskell, una función es una aplicación que toma uno o más argumentos y devuelve un valor.
En Haskell, las funciones se definen mediante ecuaciones formadas por el nombre de la función, los nombres de los argumentos y el cuerpo que especifica cómo se calcula el valor a partir de los argumentos.
Ejemplo de definición de función en Haskell:
```
doble x = x + x
```

Ejemplo de evaluación:

doble 3
= 3 + 3   [def. de doble]
= 6       [def. de +]

1.2. Evaluaciones de funciones en Haskell

Ejemplo de evaluación anidada impaciente:

doble (doble 3)
= doble (3 + 3)   [def. de doble]
= doble 6         [def. de +]
= 6 + 6           [def. de doble]
= 12              [def. de +]

Ejemplo de evaluación anidada perezosa:

doble (doble 3)
= (doble 3) + (doble 3)    [def. de doble]
= (3 +3) + (doble 3)       [def. de doble]
= 6 + (doble 3)            [def. de +]
= 6 + (3 + 3)              [def. de doble]
= 6 + 6                    [def. de +]
= 12                       [def. de +]

1.3. Comprobación de propiedades

Propiedad: El doble de x más y es el doble de x más el doble de y
- Expresión de la propiedad:
```
prop_doble x y = doble (x+y) == (doble x) + (doble y)
```
- Comprobación de la propiedad con QuickCheck:
```
λ> quickCheck prop_doble
+++ OK, passed 100 tests.
```
#+end_example
Para usar QuickCheck hay que importarlo, escribiendo al principio del fichero
```
import Test.QuickCheck
```

1.4. Refutación de propiedades

Propiedad: El producto de dos números cualesquiera es distinto de su suma.

Expresión de la propiedad:
```
prop_prod_suma x y = x*y /= x+y
```

Refutación de la propiedad con QuickCheck:

λ> quickCheck prop_prod_suma
*** Failed! Falsifiable (after 1 test):
0
0

Refinamiento: El producto de dos números no nulos cualequiera es distinto de su suma.
```
prop_prod_suma' x y =
    x /= 0 && y /= 0 ==> x*y /= x+y
```

Refutación de la propiedad con QuickCheck:

λ> quickCheck prop_prod_suma'
+++ OK, passed 100 tests.
λ> quickCheck prop_prod_suma'
*** Failed! Falsifiable (after 5 tests):
2
2

2. Programación funcional y programación imperativa

La programación funcional es un estilo de programación cuyo método básico de computación es la aplicación de funciones a sus argumentos.
Un lenguaje de programación funcional es uno que soporta y potencia el estilo funcional.
La programación imperativa es un estilo de programación en el que los programas están formados por instrucciones que especifican cómo se ha de calcular el resultado.

Ejemplo de problema para diferenciar los estilos de programación: Sumar los n primeros números.

Solución mediante programación imperativa (con Python)

def suma(n):
    contador = 0
    total    = 0
    while contador < n:
        contador = contador + 1
        total    = total + contador
    return total

Evaluación de suma(4):

contador total

0 0

1 1

2 3

3 6

4 10
Solución mediante programación funcional
```
suma n = sum [1..n]
```

contador	total
0	0
1	1
2	3
3	6
4	10

Evaluación de suma 4:

suma 4
= sum [1..4]        [def. de suma]
= sum [1, 2, 3, 4]  [def. de [..]]
= 1 + 2 + 3 + 4     [def. de sum]
= 10                [def. de +]

3. Rasgos característicos de Haskell

Programas concisos.
Sistema potente de tipos.
Listas por comprensión.
Funciones recursivas.
Funciones de orden superior.
Razonamiento sobre programas.
Evaluación perezosa.
Efectos monádicos.

4. Antecedentes históricos

1930s: Alonzo Church desarrolla el lambda cálculo (teoría básica de los lenguajes funcionales).
1950s: John McCarthy desarrolla el Lisp (lenguaje funcional con asignaciones).
1960s: Peter Landin desarrolla ISWIN (lenguaje funcional puro).
1970s: John Backus desarrolla FP (lenguaje funcional con orden superior).
1970s: Robin Milner desarrolla ML (lenguaje funcional con tipos polimórficos e inferencia de tipos).
1978 John Backus: Can programming be liberated from the von Neumann style?
1980s: David Turner desarrolla Miranda (lenguaje funcional perezoso).
1987: Un comité comienza el desarrollo de Haskell.
1990: Haskell 1.0.
1991: Haskell 1.1 (sintaxis let, secciones).
1992: Haskell 1.2, GHC.
1996: Haskell 1.3 (Mónadas, sintaxis do, mejora en el sistema de tipos).
1999: Haskell 98.
2000s: Desarrollo de GHC, extensiones del lenguaje.
2003: El comité publica el "Haskell Report".
2009: The Haskell 2010 standard
2010s: Desarrolo de GHC, Haskell Platform, Haskell Stack.

5. Presentación de Haskell

5.1. Ejemplo de recursión sobre listas

Especificación: (sum xs) es la suma de los elementos de xs.
Ejemplo:
```
sum [2,3,7] == 12
```
Definición:
```
sum []     = 0
sum (x:xs) = x + sum xs
```

Evaluación:

sum [2,3,7]
= 2 + sum [3,7]           [def. de sum]
= 2 + (3 + sum [7])       [def. de sum]
= 2 + (3 + (7 + sum []))  [def. de sum]
= 2 + (3 + (7 + 0))       [def. de sum]
= 12                      [def. de +]

Tipo de sum: (Num a) => [a] -> a

5.2. Ejemplo con listas de comprensión

Especificación: (ordena xs) es la lista obtenida ordenando xs mediante el algoritmo de ordenación rápida.

Ejemplo:

ordena [4,6,2,5,3] == [2,3,4,5,6]
ordena "deacb"     == "abcde"

Definición:

ordena [] = []
ordena (x:xs) =
  (ordena menores) ++ [x] ++ (ordena mayores)
  where menores = [a | a <- xs, a <= x]
        mayores = [b | b <- xs, b > x]

Tipo de ordena: Ord a => [a] -> [a]

Evaluación del ejemplo con listas de comprensión

ordena [4,6,2,3]
= (ordena [2,3]) ++ [4] ++ (ordena [6])
  [def. ordena]
= ((ordena []) ++ [2] ++ (ordena [3])) ++ [4] ++ (ordena [6])
  [def. ordena]
= ([] ++ [2] ++ (ordena [3])) ++ [4] ++ (ordena [6])
  [def. ordena]
= ([2] ++ (ordena [3])) ++ [4] ++ (ordena [6,5])
  [def. ++]
= ([2] ++ ((ordena []) ++ [3] ++ [])) ++ [4] ++ (ordena [6])
  [def. ordena]
= ([2] ++ ([] ++ [3] ++ [])) ++ [4] ++ (ordena [6])
  [def. ordena]
= ([2] ++ [3]) ++ [4] ++ (ordena [6])
  [def. ++]
= [2,3] ++ [4] ++ (ordena [6])
  [def. ++]
= [2,3,4] ++ (ordena [6])
  [def. ++]
= [2,3,4] ++ ((ordena []) ++ [6] ++ (ordena []))
  [def. ordena]
= [2,3,4] ++ ((ordena []) ++ [6] ++ (ordena []))
  [def. ordena]
= [2,3,4] ++ ([] ++ [6] ++ [])
  [def. ordena]
= [2,3,4,6]
  [def. ++]

6. Material complementario

El código del tema se encuentra en este enlace.

Este tema también se encuentra en los siguientes formatos:

Como transparencias en PDF.
Como libro interactivo en IHaskell sobre Jupyter.
Como vídeos de clase: vídeo 1 y vídeo 2.

7. Bibliografía

R. Bird. Introducción a la programación funcional con Haskell. Prentice Hall, 2000.
- Cap. 1: Conceptos fundamentales.
G. Hutton Programming in Haskell. Cambridge University Press, 2007.
- Cap. 1: Introduction.
J. Kaasinen, J. Lång. Haskell MOOC University of Helsinki.
- Lecture 1: … And so It begins
B. O'Sullivan, D. Stewart y J. Goerzen Real World Haskell. O'Reilly, 2008.
- Cap. 1: Getting started.
B.C. Ruiz, F. Gutiérrez, P. Guerrero y J.E. Gallardo. Razonando con Haskell. Thompson, 2004.
- Cap. 1: Programación funcional.
S. Thompson. Haskell: The craft of functional programming, Second Edition. Addison-Wesley, 1999.
- Cap. 1: Introducing functional programming.