orden - haskell ejemplos

¿Estoy usando el razonamiento de sonido ecuacional sobre una definición de filtro en términos de foldr?

Question

bueno, esta es la definición de la función de filtro usando foldr:

myFilter p xs = foldr step [] xs
    where step x ys | p x       = x : ys
                    | otherwise = ys

así que, por ejemplo, digamos que tengo esta función:

myFilter odd [1,2,3,4]

Así será:

foldr step [] [1,2,3,4]

y esto será

step 1 (foldr step [] [2,3,4])

y esto será

step 1 (step 2 (foldr step [] [3,4]))

y esto será

step 1 (step 2 (step 3 (foldr step [] [4])))

y esto será

step 1 (step 2 (step 3 (step 4 (foldr step [] []))))

y foldr step [] [] es [] así que:

step 1 (step 2 (step 3 (step 4 [])))

ahora entraremos en la función de step .
Aquí está la definición de step dentro de la función myFilter , desde arriba:

step x ys | p x       = x : ys
          | otherwise = ys

también, te recuerdo que p es realmente la función odd en nuestro ejemplo.

Bueno, de nuevo, estamos aquí:

step 1 (step 2 (step 3 (step 4 [])))

y

x = 4 en el step más interno, y 4 no es impar, entonces ys , que es []

así que ahora tenemos esto:

step 1 (step 2 (step 3 []))

ahora, en el step más interno, x = 3 y 3 es impar, entonces devolvemos x:ys , que es 3 : [] , que es [3] , y ahora obtenemos:

step 1 (step 2 [3])

y ahora, en el step interno, x = 2 y 2 no es impar, entonces devolvemos ys , que es [3] , así que ahora obtendremos:

step 1 [3]

y ahora, x = 1 , y 1 es impar, entonces devolvemos x : ys , que es 1 : [3] , que es [1,3] .

El fin :-).

estoy en lo cierto en todos mis movimientos?
muchas gracias :-).

ps la definición de myFilter proviene del libro Real World Haskell , en el capítulo 4.

Answer 1

A primera vista, los pasos que ha tomado en su ejemplo específico se ven correctos individualmente. Sin embargo, me gustaría señalar que tanto el filter como el foldr pueden aplicarse de manera útil a listas infinitas, lo que debería indicar que el orden de los pasos es incorrecto en lo que respecta a Haskell.

Answer 2

Esto me parece bien en la primera lectura.

Sin embargo, lo importante es recordar que para lograr una evaluación perezosa, Haskell realmente verá las cosas de otra manera. En otras palabras, la secuencia real se parece más a

step 1 (step 2 (step 3 (step 4 [])))

se convierte

step 1 <block1>

que se convierte

[1, <block1>]

entonces, si tratas de sacar el siguiente elemento de esa lista, se evaluará

[1, step 2 <block2>]

que se convierte

[1, <block2>]

y luego tratando de evaluar

[1, step 3 (step 4 [])]

se convierte en

[1, step 3 <block3>]

que se convierte

[1, 3, <block3>]

Esto me llevó un tiempo entenderlo. Era contradictorio para mí que, dado que foldr parece ser evaluado desde el "adentro hacia afuera", pero foldl se evalúa desde el "afuera en" que foldr sería flojo (lo cual es), mientras que foldl es estricto. Pero si lo piensas de la manera que describí arriba, tiene sentido (para mí, de todos modos).

Answer 3

Solo para ampliar el orden de evaluación diferida: básicamente, Haskell siempre evalúa la función primero, sin mirar los argumentos hasta que no tenga que hacerlo.

Si se utiliza el resultado de la llamada a myFilter (por ejemplo, impreso), la función se evaluará en el siguiente orden:

myFilter odd [1,2,3,4]

Primero se myFilter función myFilter :

foldr step [] [1,2,3,4]

Ahora foldr es la función más externa y se evalúa:

step 1 (foldr step [] [2,3,4])

Ahora el step se evalúa produciendo un 1 , ya que 1 es impar:

1 : foldr step [] [2,3,4]

Ahora, el primer elemento de la lista de resultados está disponible y puede ser utilizado por la función de llamada. Si la función de llamada también utiliza los siguientes elementos, la evaluación continúa con el foldr :

1 : step 2 (foldr step [] [3,4])

La evaluación del step ahora no produce ningún elemento nuevo, ya que 2 es par:

1 : foldr step [] [3,4]

Entonces foldr nuevamente:

1 : step 3 (foldr step [] [4])

Ahora el step evaluación produce 3 :

1 : 3 : foldr step [] [4]

Evaluando foldr ;

1 : 3 : step 4 (foldr step [] [])

Y step una vez más:

1 : 3 : foldr step [] []

Finalmente foldr evalúa a una lista vacía:

1 : 3 : []