PDF de programación - 2013 Temas de "Programación funcional" con Haskell

Temas de “Programación funcional”

(curso 2012–13)

José A. Alonso Jiménez

Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
Sevilla, 26 de Septiembre de 2012

Esta obra está bajo una licencia Reconocimiento–NoComercial–CompartirIgual 2.5 Spain
de Creative Commons.

Se permite:

copiar, distribuir y comunicar públicamente la obra

hacer obras derivadas

Bajo las condiciones siguientes:

Reconocimiento. Debe reconocer los créditos de la obra de la manera espe-
cificada por el autor.

No comercial. No puede utilizar esta obra para fines comerciales.

Compartir bajo la misma licencia. Si altera o transforma esta obra, o genera
una obra derivada, sólo puede distribuir la obra generada bajo una licencia
idéntica a ésta.

Al reutilizar o distribuir la obra, tiene que dejar bien claro los términos de la licen-
cia de esta obra.

Alguna de estas condiciones puede no aplicarse si se obtiene el permiso del titular
de los derechos de autor.

Esto es un resumen del texto legal (la licencia completa). Para ver una copia de esta
licencia, visite http://creativecommons.org/licenses/by-nc-sa/2.5/es/ o envie una
carta a Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Índice general

3

4

Tema 1

Introducción a la programación
funcional

1.1. Funciones

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
= 6

[def. de doble]
[def. de +]

Evaluaciones de funciones en Haskell

Ejemplo de evaluación anidada impaciente:

doble (doble 3)

= doble (3 + 3)
= doble 6
= 6 + 6
= 12

[def. de doble]
[def. de +]
[def. de doble]
[def. de +]

5

6

Ejemplo de evaluación anidada perezosa:

doble (doble 3)

= (doble 3) + (doble 3)
= (3 +3) + (doble 3)
= 6 + (doble 3)
= 6 + (3 + 3)
= 6 + 6
= 12

[def. de doble]
[def. de doble]
[def. de +]
[def. de doble]
[def. de +]
[def. de +]

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:

*Main> quickCheck prop_doble
+++ OK, passed 100 tests.

Para usar QuickCheck hay que importarlo, escribiendo al principio del fichero

import Test.QuickCheck

Refutación de propiedades

Propiedad: El producto de dos números cualequiera 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:

*Main> 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.

Tema 1.

Introducción a la programación funcional

7

prop_prod_suma' x y =

x /= 0 && y /= 0 ==> x*y /= x+y

Refutación de la propiedad con QuickCheck:

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

1.2. Programación funcional

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 progra-
mas 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

Programa suma n:

contador := 0
total := 0
repetir

contador := contador + 1
total := total + contador

hasta que contador = n

8

Evaluación de suma 4:

contador

total

0
1
2
3
4

0
1
3
6
10

Solución mediante programación funcional

Programa:

suma n = sum [1..n]

Evaluación de suma 4:

suma 4

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

[def. de suma]
[def. de [..]]
[def. de sum]
[def. de +]

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

Tema 1.

Introducción a la programación funcional

9

1.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”.

1.5. Presentación de Haskell

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 []
sum (x:xs) = x + sum xs

= 0

Evaluación:

sum [2,3,7]

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

[def. de sum]
[def. de sum]
[def. de sum]
[def. de sum]
[def. de +]

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

10

Ejemplo con listas de comprensión

Especificación: (ordena xs) es la lista obtenida ordenando xs mediante el algorit-
mo 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])
= ((ordena []) ++ [2] ++ (ordena [3])) ++ [4] ++ (ordena [6])
= ([] ++ [2] ++ (ordena [3])) ++ [4] ++ (ordena [6])
= ([2] ++ (ordena [3])) ++ [4] ++ (ordena [6,5])
= ([2] ++ ((ordena []) ++ [3] ++ [])) ++ [4] ++ (ordena [6])
= ([2] ++ ([] ++ [3] ++ [])) ++ [4] ++ (ordena [6])
= ([2] ++ [3]) ++ [4] ++ (ordena [6])
= [2,3] ++ [4] ++ (ordena [6])
= [2,3,4] ++ (ordena [6])
= [2,3,4] ++ ((ordena []) ++ [6] ++ (ordena []))
= [2,3,4] ++ ((ordena []) ++ [6] ++ (ordena []))
= [2,3,4] ++ ([] ++ [6] ++ [])
= [2,3,4,6]

[def. ordena]
[def. ordena]
[def. ordena]
[def. ++]
[def. ordena]
[def. ordena]
[def. ++]
[def. ++]
[def. ++]
[def. ordena]
[def. ordena]
[def. ordena]
[def. ++]

Bibliografía

1. R. Bird. Introducción a la programación funcional con Haskell. Prentice Hall, 2000.

Cap. 1: Conceptos fundamentales.

2. G. Hutton Programming in Haskell. Cambridge University Press, 2007.

Tema 1.

Introducción a la programación funcional

11

Cap. 1: Introduction.

3. B. O’Sullivan, D. Stewart y J. Goerzen Real World Haskell. O’Reilly, 2008.

Cap. 1: Getting Started.

4. B.C. Ruiz, F. Gutiérrez, P. Guerrero y J.E. Gallardo. Razonando con Haskell. Thom-

pson, 2004.

Cap. 1: Programación funcional.

5. S. Thompson. Haskell: The Craft of Functional Programming, Second Edition. Addison-

Wesley, 1999.

Cap. 1: Introducing functional programming.

12

Tema 2

Introducción a la programación con
Haskell

2.1. El sistema GHC

El sistema GHC

Los programa funcionales pueden evaluarse manualmente (como en el tema an-
terior).

Los lenguajes funcionales evalúan automáticamente los programas funcionales.

Haskell es un lenguaje funcional.

GHC (Glasgow Haskell Compiler) es el intérprete de Haskell que usaremos en el
curso.

2.2.

Iniciación a GHC

2.2.1.

Inicio de sesión con GHCi

Inicio mediante ghci

I1M> ghci
GHCi, version 6.10.3: http://www.haskell.org/ghc/
Prelude>

:? for help

La llamada es Prelude>

Indica que ha cargado las definiciones básicas que forman el preludio y el sistema
está listo para leer una expresión, evaluarla y escribir su resultado.

13

14

2.2.2. Cálculo aritmético
Cálculo aritmético: Operaciones aritméticas

Operaciones aritméticas en Haskell:

Prelude> 2+3
5
Prelude> 2-3
-1
Prelude> 2*3
6
Prelude> 7 `div` 2
3
Prelude> 2^3
8

Cálculo aritmético: Precedencia y asociatividad

Precedencia:

Prelude> 2*10^3
2000
Prelude> 2+3*4
14

Asociacitividad:

Prelude> 2^3^4
2417851639229258349412352
Prelude> 2^(3^4)
2417851639229258349412352
Prelude> 2-3-4
-5
Prelude> (2-3)-4
-5

2.2.3. Cálculo con listas
Cálculo con listas: Seleccionar y eliminar

Seleccionar el primer elemento de una lista no vacía:

head [1,2,3,4,5] ; 1

Tema 2.

Introducción a la programación con Haskell

15

Eliminar el primer elemento de una lista no vacía:

tail [1,2,3,4,5] ; [2,3,4,5]

Seleccionar el n–ésimo elemento de una lista (empezando en 0):

[1,2,3,4,5] !! 2 ; 3

Seleccionar los n primeros elementos de una lista:

take 3 [1,2,3,4,5] ; [1,2,3]

Eliminar los n primeros elementos de una lista:

drop 3 [1,2,3,4,5] ; [4,5]

Cálculo con listas

Calcular la longitud de una lista:

length [1,2,3,4,5] ; 5

Calcular la suma de una lista de números:

sum [1,2,3,4,5] ; 15

Calcular el producto de una lista de números:

product [1,2,3,4,5] ; 120

Concatenar dos listas:

[1,2,3] ++ [4,5] ; [1,2,3,4,5]

Invertir una lista:

reverse [1,2,3,4,5] ; [5,4,3,2,1]

2.2.4. Cálculos con errores
Ejemplos de cálculos con errores

Prelude> 1 `div` 0
*** Exception: divide by zero
Prelude> head []
*** Exception: Prelude.head: empty list
Prelude> tail []

16

*** Exception: Prelude.tail: empty list
Prelude> [2,3] !! 5
*** Exception: Prelude.(!!): index too large

2.3. Aplicación de funciones

Aplicación de funciones en matemáticas y en Haskell

Notación para funciones en matemáticas:

• En matemáticas, la aplicación de f