ProgFunc: Ejercicios de repaso - Evaluación perezosa

Buenas!

No entiendo bien por qué se da lo siguiente:

===============================================

Dadas las siguientes definiciones:

a = map repeat b
b = 1 : map (+1) b

Indique el resultado de evaluar take 8 a:

Seleccione una:

[1,2,3,4,5,6,7,8]

[1,2,4,8,16,32,64,128]

[1,1,1,1,1,1,1,1] Incorrecta

¿Cómo afecta map (+1) a su evaluación?

Diverge

La respuesta correcta es: Diverge

===============================================

Los pasos que hice fueron:

take 8 a
take 8 (map repeat b)
take 8 (map repeat (1 : map (+1) b))
take 8 (repeat 1 : map repeat (map (+1) b))
take 8 (1 : repeat 1 : map repeat (map (+1) b))
take 7 (repeat 1 : map repeat (map (+1) b))
...
etc

En qué le estoy errando?

Gracias!

Re: Ejercicios de repaso - Evaluación perezosa

de Germán Ferrari - sábado, 11 de julio de 2020, 11:27

Hola.

Le estás errando en la reducción de take. Hago la evaluación paso a paso para que lo veas.

Copio las implementaciones de las funciones involucradas para referencia:

map :: (a -> b) -> [a] -> [b]
map _ []       = []
map f (x : xs) = f x : map f xs

repeat :: a -> [a]
repeat x = x : repeat x

take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ []         = []
take n (x : xs)   = x : take (n - 1) xs

Inicialmente podemos intentar reducir take que es la aplicación más externa, pero todavía no podemos porque 8 no es <= 0 y en el segundo argumento no observamos ni [] ni :. Lo único que tenemos para reducir es a.

take 8 a
take 8 (map repeat b)

La expresión map repeat b no tiene un constructor en la parte más externa, por lo que seguimos sin poder reducir el take. Intentamos reducir map pero tampoco
podemos porque porque en el segundo argumento no observemos ni [] ni :. Así que seguimos por lo único que tenemos para reducir que es b.

take 8 a
take 8 (map repeat b)
take 8 (map repeat (1 : map (+1) b))

La expresión 1 : map (+1) b tiene un : en la parte más externa, por lo que ahora si podemos avanzar un paso en la evaluación de map.

take 8 a
take 8 (map repeat b)
take 8 (map repeat (1 : map (+1) b))
take 8 (repeat 1 : map repeat (map (+1) b))

Y ahora si tenemos un : en la parte más externa del segundo argumento del take (repeat 1 : map repeat (map (+1) b)), por lo que podemos avanzar un paso en su evaluación.

take 8 a
take 8 (map repeat b)
take 8 (map repeat (1 : map (+1) b))
take 8 (repeat 1 : map repeat (map (+1) b)) 
repeat 1 : take (8 - 1) (map repeat (map (+1) b))

En este punto aparece la diferencia con los pasos de evalución que pusiste.

La acuación por la que se está reduciendo take es:

take n (x : xs)   = x : take (n - 1) xs

A vos te está faltando la parte del x : de la expresión de la derecha.

En este punto ya se puede ver que la expresión divergue, porque para evaluarla completamente no te salvás de evaluar repeat 1 que diverge.

Saludos,
Germán.

Re: Ejercicios de repaso - Evaluación perezosa

de Agustin Gallego Leon - sábado, 11 de julio de 2020, 13:13

Impecable, gracias!

Tengo otra duda de un ejercicio similar, pero con foldr.

===============================================

Dada la siguiente definición:

a = 1 : foldr (\x xs -> 1 + x : xs) [] a

¿Cuál es el resultado de evaluar take 4 a?

Seleccione una:

Diverge

¿Cuántos elementos de una lista debo evaluar para computar take 4?

[1,2,3,4]

[4,3,2,1]

[1]

===============================================

Cualquiera sea la reducción que haga de foldr, me da [1,2,2,2] el resultado (ya sea tomando a medida que se van generando, o esperando a generar un largo 3 con el foldr). Cómo serían bien los pasos para este ejercicio?

Re: Ejercicios de repaso - Evaluación perezosa

de Germán Ferrari - sábado, 11 de julio de 2020, 15:07

El razonamiento es el mismo, solo que las expresiones son un poco más complicadas en este caso. Hay que tratar de no marearse.

Funciones usadas para referencia:

take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ []         = []
take n (x : xs)   = x : take (n - 1) xs

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f e []       = e
foldr f e (x : xs) = f x (foldr f e xs)

Siguiendo el mismo razonamiento que antes, intentamos reducir take pero no podemos porque necesitaríamos un constructor en la parte más externa de la expresión del segundo argumento, y por ahora tenemos solo a. Lo único que podemos empezar reduciendo es a.

take 4 a
take 4 (1 : foldr (\x xs -> 1 + x : xs) [] a)

Ahora si estamos en condiciones de reducir take usando la tercer ecuación.

take 4 a
take 4 (1 : foldr (\x xs -> 1 + x : xs) [] a)
1 : take (4 - 1) (foldr (\x xs -> 1 + x : xs) [] a)

Intentamos reducir take nuevamente y nos va a llevar a reducir 4 - 1 para poder determinar si es <= 0, lo que no se cumple. No podemos reducir take porque en el segundo argumento no tenemos un constructor en la parte más externa.

Intentamos reducir foldr (\x xs -> 1 + x : xs) [] a. Mirando la definición de foldr vemos que para reducirla necesitamos un constructor en la parte más externa del tercer argumento, que en este caso es a, por lo que tampoco podemos reducir foldr. Lo siguiente a intentar reducir es a que si puede reducirse.

take 4 a
take 4 (1 : foldr (\x xs -> 1 + x : xs) [] a)
1 : take (4 - 1) (foldr (\x xs -> 1 + x : xs) [] a)
1 : take      3  (foldr (\x xs -> 1 + x : xs) [] (1 : foldr (\x xs -> 1 + x : xs) [] a))

Ahora si podemos reducir el foldr porque tenemos un : en la parte más externa de su tercer argumento. Usamos la segunda ecuación.

Capaz que es un poco difícil de ver, por lo que hago este paso más despacio.

La expresión que estamos reduciendo en este paso es:

foldr (\x xs -> 1 + x : xs) [] (1 : foldr (\x xs -> 1 + x : xs) [] a)

y la ecuación que estamos en condiciones de usar de la definición de foldr es esta:

foldr f e (x : xs) = f x (foldr f e xs)

Entonces tenemos:

(del lado izquierdo)

f = \x xs -> 1 + x : xs
e = []
x = 1
xs = foldr (\x xs -> 1 + x : xs) [] a

(del lado derecho)

foldr f e xs = foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a)
f x (foldr f e xs) = 1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a)

Por lo que la expresión original se reduce en 1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a).

take 4 a
take 4 (1 : foldr (\x xs -> 1 + x : xs) [] a)
1 : take (4 - 1) (foldr (\x xs -> 1 + x : xs) [] a)
1 : take      3  (foldr (\x xs -> 1 + x : xs) [] (1 : foldr (\x xs -> 1 + x : xs) [] a))
1 : take      3  (1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))

Ahora volvemos a estar en condiciones de reducir el take que es la aplicación más externa.

take 4 a
take 4 (1 : foldr (\x xs -> 1 + x : xs) [] a)
1 : take (4 - 1) (foldr (\x xs -> 1 + x : xs) [] a)
1 : take      3  (foldr (\x xs -> 1 + x : xs) [] (1 : foldr (\x xs -> 1 + x : xs) [] a))
1 : take      3  (1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))
1 : 1 + 1 : take (3 - 1) (foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))

Siguiendo los mismos razonamientos que antes, tenemos que reducir nuevamente a.

take 4 a
take 4 (1 : foldr (\x xs -> 1 + x : xs) [] a)
1 : take (4 - 1) (foldr (\x xs -> 1 + x : xs) [] a)
1 : take      3  (foldr (\x xs -> 1 + x : xs) [] (1 : foldr (\x xs -> 1 + x : xs) [] a))
1 : take      3  (1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))
1 : 1 + 1 : take (3 - 1) (foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))
1 : 1 + 1 : take      2  (foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] (1 : foldr (\x xs -> 1 + x : xs) [] a)))

Más allá de que la expresión queda complicada, el razonamiento que se sigue es el mismo que antes. Ahora estamos en condiciones de reducir foldr (\x xs -> 1 + x : xs) [] (1 : foldr (\x xs -> 1 + x : xs) [] a), que es la misma expresión que teníamos antes, podemos reutilizar la reducción anterior.

take 4 a
take 4 (1 : foldr (\x xs -> 1 + x : xs) [] a)
1 : take (4 - 1) (foldr (\x xs -> 1 + x : xs) [] a)
1 : take      3  (foldr (\x xs -> 1 + x : xs) [] (1 : foldr (\x xs -> 1 + x : xs) [] a))
1 : take      3  (1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))
1 : 1 + 1 : take (3 - 1) (foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))
1 : 1 + 1 : take      2  (foldr (\x xs -> 1 + x : xs) [] (1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a)))

El paso siguiente de la evaluación es reducir foldr (\x xs -> 1 + x : xs) [] (1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a)).

Comparado con la reducción que hicimos antes del foldr, cambian quienes son
x y xs:

x = 1 + 1
xs = foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a)

Luego de aplicar el paso de reducción queda: 1 + 1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a)

Integrando todo:

take 4 a
take 4 (1 : foldr (\x xs -> 1 + x : xs) [] a)
1 : take (4 - 1) (foldr (\x xs -> 1 + x : xs) [] a)
1 : take      3  (foldr (\x xs -> 1 + x : xs) [] (1 : foldr (\x xs -> 1 + x : xs) [] a))
1 : take      3  (1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))
1 : 1 + 1 : take (3 - 1) (foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))
1 : 1 + 1 : take      2  (foldr (\x xs -> 1 + x : xs) [] (1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a)))
1 : 1 + 1 : take      2  (1 + 1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))

Reduciendo take tenemos:

take 4 a
take 4 (1 : foldr (\x xs -> 1 + x : xs) [] a)
1 : take (4 - 1) (foldr (\x xs -> 1 + x : xs) [] a)
1 : take      3  (foldr (\x xs -> 1 + x : xs) [] (1 : foldr (\x xs -> 1 + x : xs) [] a))
1 : take      3  (1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))
1 : 1 + 1 : take (3 - 1) (foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))
1 : 1 + 1 : take      2  (foldr (\x xs -> 1 + x : xs) [] (1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a)))
1 : 1 + 1 : take      2  (1 + 1 + 1 : foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))
1 : 1 + 1 : 1 + 1 + 1 : take (2 - 1) (foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] (foldr (\x xs -> 1 + x : xs) [] a))

Como se puede ir viendo, la lista que se va produciendo suma uno al elemento anterior. Si continuás con los pasos de reducción vas a llegar a [1,2,3,4].

Re: Ejercicios de repaso - Evaluación perezosa

de Agustin Gallego Leon - sábado, 11 de julio de 2020, 17:06

Tremenda respuesta :) Quedó clarísimo, muchas gracias!!

Me estaba comiendo dejar los foldr parcialmente aplicados, que son los que luego van sumando +1 a los 1 generados por "a", y estaba haciendo mal la recursión.