Cómo evaluar ejercicio de repaso de lazy evaluation de recorreL

Cómo evaluar ejercicio de repaso de lazy evaluation de recorreL

de Diego Javier Rodriguez Uranga -
Número de respuestas: 6

Buenas! Sobre el siguiente ejercicio, no estoy comprendiendo por qué recorreL sí genera resultados, pongo mi proceso debajo de la letra del ejercicio:


Dadas las siguientes definiciones:

data Arbol a = Vacio | Nodo (Arbol a) a (Arbol a)
genera = fst $ generaAux 0
  where generaAux n  =  let  (l,n' )  = generaAux (n+1)
                             (r,n'')  = generaAux n'
                        in   (Nodo  l n r, n'')
recorreL  (Nodo l x _)  = x : recorreL l
recorreL  Vacio         = []
recorreR  (Nodo _ x r)  = x : recorreR r
recorreR  Vacio         = []

¿Cuál es el resultado de evaluar head . tail $ zip (recorreL genera) (recorreR genera)?


Más allá del resultado final, centrándome en "recorreL genera", mis pasos son los siguientes:

1) recorreL genera
2) recorreL (fst $ generaAux 0)
3) recorreL (fst $ let (l, n') = generaAux (1); (r, n'') = generaAux n'; in (Nodo l 0 r, n''))
4) recorreL (fst $ 
                         let (l, n') =  (let (l, n') = generaAux (2)
                                                 (r, n'') = generaAux n'
                                             in (Nodo l 1 r', n'')
                                            )
                              (r, n'') = generaAux n'
                        in (Nodo l 0 r, n'')
                     )

Y así sucesivamente abriendo el primer generaAux sin parar, ya que recorreL necesita un (Nodo l x _) para matchear, pero esta función nunca termina de retornar un Nodo así, nunca termina de dar una expresión clara para el l, o al menos no entiendo cómo anotarlo o cómo funciona ya que no vi ningún otro ejemplo así. 

Sin embargo sé que si hago (take 5 (recorreL genera)) devuelve [0,1,2,3,4] por lo cual de alguna forma está haciendo la sustitución, sólo que no entiendo cómo ya que nunca termina de matchear. Cómo funciona esto?





En respuesta a Diego Javier Rodriguez Uranga

Re: Cómo evaluar ejercicio de repaso de lazy evaluation de recorreL

de Luis Sierra -
hola diego,

tu paso 4 no correcto. habría que computar fst.

4') recorreL (let (l, n') = generaAux (1); (r, n'') = generaAux n'; in Nodo l 0 r)
(CORREGIDA LA LINEA ANTERIOR; se referencia más adelante en el hilo)

ahora recorreL puede computar, porque sabe que su argumento es un Nodo

5') 0: recorreL (let (l, n') = generaAux 1; in l)

o sea,

5'') 0: recorreL (fst $ generaAux 1)

y luego sigue con los restantes naturales.

luis
En respuesta a Luis Sierra

Re: Cómo evaluar ejercicio de repaso de lazy evaluation de recorreL

de Diego Javier Rodriguez Uranga -
Gracias!

Sigo medio confundido pero necesitaría ver la implementación de haskell me suena para terminar de entenderlo, como que hace muuchos saltos ahí que no imagino cómo los hace. O sea, entiendo capaz cómo yo una persona puedo ir saltando por lugares y haciéndolos, pero no la estructura interna que hace que haskell logre hacer esos saltos, no parecen sencillos y directos como eran en los otros ejemplos que había visto hasta ahora.
En respuesta a Luis Sierra

Re: Cómo evaluar ejercicio de repaso de lazy evaluation de recorreL

de Nicolas Eduardo Navascues Soto -
Buenas!
Con respecto al paso 4', qué fue exactamente lo que se obtuvo al realizar la computación de fst? No me doy cuenta la diferencia entre el paso 3 y el paso 4', más allá de que ya no aparece "fst".
Y en el caso de evaluar recorreR, los pasos serían iguales hasta llegar al paso 5', donde en este caso sería
5') 0: recorreR (let (r, n'') = generaAux n' in r) ? No me queda del todo claro.

Gracias
En respuesta a Nicolas Eduardo Navascues Soto

Re: Cómo evaluar ejercicio de repaso de lazy evaluation de recorreL

de Luis Sierra -
hola nicolás,

puede ser que no entiendas el paso 4' porque... no lo escribí bien. tendría que haber puesto

4') recorreL (let (l, n') = generaAux (1); (r, n'') = generaAux n'; in Nodo l 0 r

pero le erré en el copy/paste.

miremos de vuelta ...

3) recorreL (fst $ let (l, n') = generaAux (1); (r, n'') = generaAux n'; in (Nodo l 0 r, n''))

lo primero que se intenta reducir es el recorreL; pero para hacerlo, necesita saber si su argumento es un Node o es Vacio, y lo que ve es que es un fst $ de algo.

así que intenta reducir el fst. en 2) el fst se aplicaba a generaAux 0, y como no sabía que era eso, debía reducir el generaAux. pero ahora, en 3), el fst se aplica a una cosa que es let blablabla in (izq, der). así que sabemos que tenemos un par, y que de ese par me interesa izq. es cierto que hay alguna declaración con let, pero sólo se tomarán en cuenta si son necesarias para computar izq. por eso, 4') computa el fst dejando Nodo l 0 r del par original.

mejor?

luis
En respuesta a Nicolas Eduardo Navascues Soto

Re: Cómo evaluar ejercicio de repaso de lazy evaluation de recorreL

de Luis Sierra -
el caso de recorreR es diferente...

1) recorreR genera
2) recorreR (fst $ generaAux 0)
3) recorreR (fst $ let (l, n') = generaAux (1); (r, n'') = generaAux n'; in (Nodo l 0 r, n''))
4) recorreR (let (l, n') = generaAux (1); (r, n'') = generaAux n'; in Nodo l 0 r
5) 0: recorreR (let (l, n') = generaAux 1; (r, n'') = generaAux n'; in r)

observá que el paso 4 sigue siendo el mismo; la reducción del fst. y el 5 es la reducción del recorreR. pero a diferencia de la otra situación, ahora lo que hay que devolver es r, y no l. como calcular r depende del cálculo de n', debo computar generaAux 1; y luego generaAux 2, etc, pero nunca voy a obtener un primer valor para devolver.

así que mientras recorreL inspecciona la "rama más a la izquierda", y no precisa de las ramas derechas, recorreR precisa también generar las ramas a su izquierda para descubrir el número n' que precisa para su reducción.

mejor?

luis