Librerías auxiliares
import Test.QuickCheck
import Data.List
Estrategias de evaluación
mult :: (Int,Int) -> Int
mult (x,y) = x*y
mult (1+2,2+3)
= mult (3,5) [por def. de +]
= 3*5 [por def. de mult]
= 15 [por def. de *]
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
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 *]
Procesamiento con el infinito
inf :: Int
inf = 1 + inf
ghci> inf
C-c C-c Interrupted.
inf
= 1 + inf [por def. inf]
= 1 + (1 + inf) [por def. inf]
= 1 + (1 + (1 + inf)) [por def. inf]
= ...
Procesamiento con el infinito
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]
= ...
fst (0,inf)
= 0 [por def. fst]
ghci> fst (0,inf)
0
Número de reducciones según las estrategias
cuadrado :: Int -> Int
cuadrado n = n * n
cuadrado (1+2)
= cuadrado 3 [por def. +]
= 3*3 [por def. cuadrado]
= 9 [por def. de *]
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:
cuadrado (1+2)
= x*x con x = 1+2 [por def. cuadrado]
= 3*3 [por def. de +]
= 9 [por def. de *]
Programación con estructuras infinitas
unos
es una lista infinita de unos.unos :: [Int]
unos = 1 : unos
unos
= 1 : unos [por def. unos]
= 1 : (1 : unos) [por def. unos]
= 1 : (1 : (1 : unos)) [por def. unos]
= ...
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
head unos
= head (1 : unos) [por def. unos]
= head (1 : (1 : unos)) [por def. unos]
= head (1 : (1 : (1 : unos))) [por def. unos]
= ...
head unos
= head (1 : unos) [por def. unos]
= 1 [por def. head]
ghci> head unos
1
Programación modular
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
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
ghci> [1..]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
ghci> take 3 [1..]
[1,2,3]
ghci> filter (<=3) [1..]
[1,2,3 C-c C-c Interrupted.
ghci> 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]
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 . Por ejemplo,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]
= 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,sumaE [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
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
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
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