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:

ghci> quickCheck prop_doble
+++ OK, passed 100 tests.

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

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

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

2 Programación funcional

2.1 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.

2.2 Solución mediante programación imperativa

• Programa

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    |

2.3 Solución mediante programación funcional

• Programa:

suma n = sum [1..n]

• 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).
• 1980s: David Turner desarrolla Miranda (lenguaje funcional perezoso).
• 1987: Un comité comienza el desarrollo de Haskell.
• 2003: El comité publica el "Haskell Report".

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]

5.3 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 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.
• 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.