José A. Alonso
Departamento de Ciencias de la Computación e I.A.
Universidad de Sevilla
Sevilla, 6 de agosto de 2019
Notas:
:opt no-lint
Librerías auxiliares
import Test.QuickCheck
import Data.List
Estrategias de evaluación
mult :: (Int,Int) -> Int mult (x,y) = x*y
sesion
mult (1+2,2+3)
= mult (3,5) [por def. de +]
= 3*5 [por def. de mult]
= 15 [por def. de *]
sesion
mult (1+2,2+3)
= (1+2)*(3+5) [por def. de mult]
= 3*5 [por def. de +]
= 15 [por def. de *]
Evaluación con lambda expresiones
mult' :: Int -> Int -> Int mult' x = \y -> x*y
sesion
mult' (1+2) (2+3)
= mult' 3 (2+3) [por def. de +]
= (\y -> 3*y) (2+3) [por def. de mult']
= (\y -> 3*y) 5 [por def. de +]
= 3*5 [por def. de +]
= 15 [por def. de *]
inf :: Int
inf = 1 + inf
sesion
ghci> inf
C-c C-c Interrupted.
sesion
inf
= 1 + inf [por def. inf]
= 1 + (1 + inf) [por def. inf]
= 1 + (1 + (1 + inf)) [por def. inf]
= ...
Procesamiento con el infinito
sesion
fst (0,inf)
= fst (0,1 + inf) [por def. inf]
= fst (0,1 + (1 + inf)) [por def. inf]
= fst (0,1 + (1 + (1 + inf))) [por def. inf]
= ...
sesion
fst (0,inf)
= 0 [por def. fst]
fst (0,inf)
0
Número de reducciones según las estrategias
cuadrado :: Int -> Int
cuadrado n = n * n
sesion
cuadrado (1+2)
= cuadrado 3 [por def. +]
= 3*3 [por def. cuadrado]
= 9 [por def. de *]
sesion
cuadrado (1+2)
= (1+2)*(1+2) [por def. cuadrado]
= 3*(1+2) [por def. de +]
= 3*3 [por def. de +]
= 9 [por def. de *]
Evaluación perezosa e impaciente
En la evaluación mediante paso de parámetros por nombre los argumentos pueden evaluarse más veces que en el paso por valor.
Se puede usar punteros para compartir valores de expresiones.
La evaluación mediante paso de parámetros por nombre usando punteros para compartir valores de expresiones se llama evaluación perezosa.
La evaluación mediante paso de parámetros por valor se llama evaluación impaciente.
Evaluación perezosa del ejemplo anterior:
sesion
cuadrado (1+2)
= x*x con x = 1+2 [por def. cuadrado]
= 3*3 [por def. de +]
= 9 [por def. de *]
unos :: [Int]
unos = 1 : unos
sesion
unos
= 1 : unos [por def. unos]
= 1 : (1 : unos) [por def. unos]
= 1 : (1 : (1 : unos)) [por def. unos]
= ...
sesion
ghci> unos
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,...
Evaluación con estructuras infinitas
sesion
head unos
= head (1 : unos) [por def. unos]
= head (1 : (1 : unos)) [por def. unos]
= head (1 : (1 : (1 : unos))) [por def. unos]
= ...
sesion
head unos
= head (1 : unos) [por def. unos]
= 1 [por def. head]
head unos
1
La evaluación perezosa permite separar el control de los datos.
Para los ejemplos se considera la función
take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
sesion
take 2 unos
= take 2 (1 : unos) [por def. unos]
= 1 : (take 1 unos) [por def. take]
= 1 : (take 1 (1 : unos)) [por def. unos]
= 1 : (1 : (take 0 unos)) [por def. take]
= 1 : (1 : []) [por def. take]
= [1,1] [por notación de listas]
Terminación de evaluaciones con estructuras infinitas
sesion
ghci> [1..]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
take 3 [1..]
[1,2,3]
take 20 [1..]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
sesion
ghci> filter (<=3) [1..]
[1,2,3 C-c C-c Interrupted.
takeWhile (<=3) [1..]
[1,2,3]
La criba de Erastótenes
2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
3 5 7 9 11 13 15 ...
5 7 11 13 ...
7 11 13 ...
11 13 ...
13 ...
primos :: [Int ]
primos = criba [2..]
criba :: [Int] -> [Int]
criba (p:xs) = p : criba [x | x <- xs, x `mod` p /= 0]
take 15 primos
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
sesion
primos
= criba [2..]
= criba (2 : [3..])
= 2 : (criba [x | x <- [3..], x `mod` 2 /= 0])
= 2 : (criba (3 : [x | x <- [4..], x `mod` 2 /= 0]))
= 2 : 3 : (criba [x | x <- [4..], x `mod` 2 /= 0,
x `mod` 3 /= 0])
= 2 : 3 : (criba (5 : [x | x <- [6..], x `mod` 2 /= 0,
x `mod` 3 /= 0]))
= 2 : 3 : 5 : (criba ([x | x <- [6..], x `mod` 2 /= 0,
x `mod` 3 /= 0,
x `mod` 5 /= 0]))
= ...
Ejemplo de programa sin aplicación estricta
(sumaNE xs)
es la suma de los números de \verb|xs|. Por ejemplo,sesion
sumaNE [2,3,5] == 10
sumaNE :: [Int] -> Int
sumaNE xs = sumaNE' 0 xs
sumaNE' :: Int -> [Int] -> Int
sumaNE' v [] = v
sumaNE' v (x:xs) = sumaNE' (v+x) xs
sumaNE [2,3,5]
10
sesion
sumaNE [2,3,5]
= sumaNE' 0 [2,3,5] [por def. sumaNE]
= sumaNE' (0+2) [3,5] [por def. sumaNE']
= sumaNE' ((0+2)+3) [5] [por def. sumaNE']
= sumaNE' (((0+2)+3)+5) [] [por def. sumaNE']
= ((0+2)+3)+5 [por def. sumaNE']
= (2+3)+5 [por def. +]
= 5+5 [por def. +]
= 10 [por def. +]
Ejemplo de programa con aplicación estricta
(sumaE xs)
es la suma de los números de xs
. Por ejemplo,sesion
sumaNE [2,3,5] == 10
sumaE :: [Int] -> Int
sumaE xs = sumaE' 0 xs
sumaE' :: Int -> [Int] -> Int
sumaE' v [] = v
sumaE' v (x:xs) = (sumaE' $! (v+x)) xs
sumaNE [2,3,5]
10
sesion
sumaE [2,3,5]
= sumaE' 0 [2,3,5] [por def. sumaE]
= (sumaE' \$! (0+2)) [3,5] [por def. sumaE']
= sumaE' 2 [3,5] [por aplicación de \$!]
= (sumaE' \$! (2+3)) [5] [por def. sumaE']
= sumaE' 5 [5] [por aplicación de \$!]
= (sumaE' \$! (5+5)) [] [por def. sumaE']
= sumaE' 10 [] [por aplicación de \$!]
= 10 [por def. sumaE']
Comparación de consumo de memoria
sesion
ghci> sumaNE [1..1000000]
*** Exception: stack overflow
ghci> sumaE [1..1000000]
1784293664
ghci> :set +s
ghci> sumaE [1..1000000]
1784293664
(2.16 secs, 145435772 bytes)
Plegado estricto
foldl
en el Data.List
foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f a [] = a
foldl' f a (x:xs) = (foldl' f $! f a x) xs
sesion
ghci> foldl (+) 0 [2,3,5]
10
ghci> foldl' (+) 0 [2,3,5]
10
ghci> foldl (+) 0 [1..1000000]
*** Exception: stack overflow
ghci> foldl' (+) 0 [1..1000000]
500000500000
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.