José A. Alonso
Departamento de Ciencias de la Computación e I.A.
Universidad de Sevilla
Sevilla, 28 de julio de 2019
Notas:
:opt no-lint
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
doble 3
6
sesion
doble 3
= 3 + 3 [def. de doble]
= 6 [def. de +]
sesion
doble (doble 3)
= doble (3 + 3) [def. de doble]
= doble 6 [def. de +]
= 6 + 6 [def. de doble]
= 12 [def. de +]
sesion
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 +]
import Test.QuickCheck
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
quickCheck prop_doble
+++ OK, passed 100 tests.
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
quickCheck prop_prod_suma
*** Failed! Falsifiable (after 1 test): 0 0
prop_prod_suma' x y = x /= 0 && y /= 0 ==> x*y /= x+y
quickCheck prop_prod_suma'
+++ OK, passed 100 tests; 15 discarded.
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.
def suma(n):
contador = 0
total = 0
while contador < n:
contador = contador + 1
total = total + contador
return total
sesion
|contador | total |
|---------|-------|
|0 | 0 |
|1 | 1 |
|2 | 3 |
|3 | 6 |
|4 | 10 |
suma n = sum [1..n]
suma 4
10
sesion
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 +]
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
sum [2,3,7]
12
sesion
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 +]
algoritmo de ordenación rápida.
sesion
ordena [4,6,2,5,3] == [2,3,4,5,6]
ordena "deacb" == "abcde"
ordena :: Ord a => [a] -> [a]
ordena [] = []
ordena (x:xs) =
(ordena menores) ++ [x] ++ (ordena mayores)
where menores = [a | a <- xs, a <= x]
mayores = [b | b <- xs, b > x]
ordena [4,6,2,3]
[2,3,4,6]
sesion
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. ++]
R. Bird. Introducción a la programación funcional con Haskell. Prentice Hall, 2000.
G. Hutton Programming in Haskell. Cambridge University Press, 2007.
B. O'Sullivan, D. Stewart y J. Goerzen Real World Haskell. O'Reilly, 2008.
B.C. Ruiz, F. Gutiérrez, P. Guerrero y J.E. Gallardo. Razonando con Haskell. Thompson, 2004.
S. Thompson. Haskell: The craft of functional programming, Second Edition. Addison-Wesley, 1999.