¿Estoy usando un razonamiento equitativo de sonido 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

Entonces, 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 [] asi que:

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

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

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

Además, te recuerdo que p es en realidad el odd función en nuestro ejemplo.

Bueno, de nuevo, estamos aquí:

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

y

x = 4 en el más interior step, y 4 no es extraño, así que regresamos ys, cual es []

Así que ahora tenemos esto:

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

Ahora, en el más interior step, x = 3, y 3 es extraño, así que regresamos x:ys, cual es 3 : [], cual es [3], y ahora tenemos:

step 1 (step 2 [3])

Y ahora, en el interior step, x = 2, y 2 no es extraño, así que regresamos ys, cual es [3], así que ahora obtendremos:

step 1 [3]

y ahora, x = 1, y 1 es extraño, así que regresamos x : ys, cual es 1 : [3], cual es [1,3].

El fin :-).

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

ps la definición de myFilter es del libro Mundo real haskell, en el capítulo 4.

Answer 1

Esto me parece bien en la primera lectura.

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

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

convertirse en

step 1 <block1>

que se convierte en

[1, <block1>]

Entonces, si intenta extraer el siguiente elemento de esa lista, evaluará

[1, step 2 <block2>]

que se convierte en

[1, <block2>]

Y luego tratando de evaluar

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

se convierte en

[1, step 3 <block3>]

que se convierte en

[1, 3, <block3>]

etc. Esto me llevó un tiempo entender. Fue contradictorio para mí que desde foldr parece ser evaluado desde el "adentro hacia afuera" pero foldl se evalúa desde el "exterior en" que foldr sería perezoso (que es), mientras que foldl es estricto. Pero si lo piensas de la forma en que describí anteriormente, tiene sentido (para mí, de todos modos).

Answer 2

Solo para ampliar la orden de evaluación perezosa: básicamente Haskell siempre evalúa la función primero, sin mirar los argumentos hasta que sea necesario.

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

myFilter odd [1,2,3,4]

Primero el myFilter Se evalúa la función:

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 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 la siguiente evaluación de elementos continúa con el foldr:

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

La evaluación de step Ahora no produce ningún elemento nuevo, ya que 2 es incluso:

1 : foldr step [] [3,4]

Asi que foldr otra vez:

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

Ahora evaluando step produce 3:

1 : 3 : foldr step [] [4]

Evaluación foldr;

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

Y step una vez más:

1 : 3 : foldr step [] []

Finalmente foldr evalúa una lista vacía:

1 : 3 : []

Answer 3

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 ambos filter y foldr se puede aplicar útilmente a listas infinitas-que debe indicar que el orden de sus pasos es incorrecto en lo que respecta a Haskell.