Tema 10: Evaluación perezosa

• Para los ejemplos se considera la función

  mult :: (Int,Int) -> Int
  mult (x,y) = x*y
  

• Evaluación mediante paso de parámetros por valor (o por más internos):

  mult (1+2,2+3)
  = mult (3,5)        [por def. de +]
  = 3*5               [por def. de mult]
  = 15                [por def. de *]
  

• Evaluación mediante paso de parámetros por nombre (o por más externos):

  mult (1+2,2+3)
  = (1+2)*(3+5)       [por def. de mult]
  = 3*5               [por def. de +]
  = 15                [por def. de *]
  

• Se considera la función

  mult' :: Int -> Int -> Int
  mult' x = \y -> x*y
  

• Evaluación:

  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 *]
  

• Definición de infinito

  inf :: Int
  inf = 1 + inf
  

• Evaluación de infinito en Haskell:

  λ> inf
    C-c C-c Interrupted.
  

• Evaluación de infinito:

  inf
  = 1 + inf             [por def. inf]
  = 1 + (1 + inf)       [por def. inf]
  = 1 + (1 + (1 + inf)) [por def. inf]
  = ...
  

• Evaluación mediante paso de parámetros por valor:

  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]
  = ...
  

• Evaluación mediante paso de parámetros por nombre:

  fst (0,inf)
  = 0           [por def. fst]
  

• Evaluación Haskell con infinito:

  λ> fst (0,inf)
  0
  

• Para los ejemplos se considera la función

  cuadrado :: Int -> Int
  cuadrado n = n * n
  

• Evaluación mediante paso de parámetros por valor:

  cuadrado (1+2)
  = cuadrado 3      [por def. +]
  = 3*3             [por def. cuadrado]
  = 9               [por def. de *]
  

• Evaluación mediante paso de parámetros por nombre:

  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 *]
  

• 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 *]
  

• Haskell usa evaluación perezosa.

• unos es una lista infinita de unos.

  unos :: [Int]
  unos = 1 : unos
  

• Evaluación:

  unos
  = 1 : unos                [por def. unos]
  = 1 : (1 : unos)          [por def. unos]
  = 1 : (1 : (1 : unos))    [por def. unos]
  = ...
  

• Evaluación en Haskell:

  λ> 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 impaciente:

  head unos
  = head (1 : unos)                [por def. unos]
  = head (1 : (1 : unos))          [por def. unos]
  = head (1 : (1 : (1 : unos)))    [por def. unos]
  = ...
  

• Evaluación perezosa:

  head unos
  = head (1 : unos)   [por def. unos]
  = 1                 [por def. head]
  

• Evaluación Haskell:

  λ> 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
  

• Ejemplo de separación del control (tomar 2 elementos) de los datos (una lista infinita de unos):

  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]
  

• Ejemplo de no terminación:

  λ> [1..]
  [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
  

• Ejemplo de terminación:

  λ> take 3 [1..]
  [1,2,3]
  

• Ejemplo de no terminación:

  λ> filter (<=3) [1..]
  [1,2,3  C-c C-c Interrupted.
  

• Ejemplo de no terminación:

  λ> takeWhile (<=3) [1..]
  [1,2,3]
  

• Ejemplo con 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          ...
  

• Definición

  primos :: [Int ]
  primos = criba [2..]
  
  criba :: [Int] -> [Int]
  criba (p:xs) = p : criba [x | x <- xs, x `mod` p /= 0]
  

• Evaluación:

  take 15 primos == [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
  

• Cálculo:

  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]))
  = ...
  

• (sumaNE xs) es la suma de los números de xs. Por ejemplo,

  sumaNE [2,3,5]  ==  10
  

  La definición es

  sumaNE :: [Int] -> Int
  sumaNE xs = sumaNE' 0 xs
  
  sumaNE' :: Int -> [Int] -> Int
  sumaNE' v []     = v
  sumaNE' v (x:xs) = sumaNE' (v+x) xs
  

• Evaluación:

  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
  

  La definición es

  sumaE :: [Int] -> Int
  sumaE xs = sumaE' 0 xs
  
  sumaE' :: Int -> [Int] -> Int
  sumaE' v []     = v
  sumaE' v (x:xs) = (sumaE' $! (v+x)) xs
  

• Evaluación:

  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']
  

• La comparación es

  λ> sumaNE [1..1000000]
  *** Exception: stack overflow
  λ> sumaE [1..1000000]
  1784293664
  λ> :set +s
  λ> sumaE [1..1000000]
  1784293664
  (2.16 secs, 145435772 bytes)
  

• Versión estricta de foldl en Data.List

  foldl' :: (a -> b -> a) -> a -> [b] -> a
  foldl' f a []     = a
  foldl' f a (x:xs) = (foldl' f $! f a x) xs
  

• Comparación de plegado y plegado estricto:

  λ> foldl (+) 0 [2,3,5]
  10
  λ> foldl' (+) 0 [2,3,5]
  10
  λ> foldl (+) 0 [1..1000000]
  *** Exception: stack overflow
  λ> foldl' (+) 0 [1..1000000]
  500000500000