Recorra una función de división de listas en Haskell

Ya no necesitas buscar más por todo internet ya que llegaste al espacio indicado, contamos con la solución que deseas sin complicarte.

Solución:

Intentemos ejecutar esta función en una lista de entrada de muestra, digamos [1,2,3,4,5]:

1. Empezamos con foldr (a ~(x,y) -> (a:y,x)) ([],[]) [1,2,3,4,5]. Aquí a es el primer elemento de la lista, y (x,y) empezar como ([],[]), asi que (a:y,x) devoluciones ([1],[]).
2. El siguiente elemento de la lista de entrada es a = 2, y (x,y) = ([1],[]), asi que (a:y,x) = ([2],[1]). Tenga en cuenta que el orden de las listas ha cambiado. Cada iteración intercambiará las listas nuevamente; sin embargo, el siguiente elemento de la lista de entrada siempre se agregará a la primera lista, que es como funciona la división.
3. El siguiente elemento de la lista de entrada es a = 3, y (x,y) = ([2],[1]), asi que (a:y,x) = ([3,1],[2]).
4. El siguiente elemento de la lista de entrada es a = 4, y (x,y) = ([3,1],[2]), asi que (a:y,x) = ([4,2],[3,1]).
5. El siguiente elemento de la lista de entrada es a = 4, y (x,y) = ([4,2],[3,1]), asi que (a:y,x) = ([5,3,1],[4,2]).
6. No quedan más elementos, por lo que el valor de retorno es ([5,3,1],[4,2]).

Como muestra el tutorial, la función de división funciona manteniendo dos listas, intercambiándolas en cada iteración y agregando cada elemento de la entrada a una lista diferente.

Podemos echar un vistazo a un ejemplo. Por ejemplo, si tenemos una lista [1, 4, 2, 5]. Si procesamos así la lista, vemos que foldr se calculará como:

foldr (a ~(x,y) -> (a:y,x)) ([],[]) [1,4,2,5]

Asi que aqui a es primero el primer elemento de la lista, y luego devolverá algo como:

(1:y, x)
    where (x, y) = foldr (a ~(x,y) -> (a:y,x)) ([],[]) [4,2,5]

Nótese que aquí el (x, y) tupla es intercambiado cuando anteponemos a al primer elemento de la tupla 2.

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = foldr (a ~(x,y) -> (a:y,x)) ([],[]) [2,5]

y si seguimos haciéndolo, obtenemos así:

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:y'', x'')
          (x'', y'') = (5:y''', x''')
          (x''', y''') = foldr (a ~(x,y) -> (a:y,x)) ([],[]) []

Dado que llegamos al final de la lista, obtenemos para el foldr … ([], []) [], la tupla de 2 ([], []):

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:y'', x'')
          (x'', y'') = (5:y''', x''')
          (x''', y''') = ([],[])

Entonces x''' = [] y y''' = [], así que esto se resuelve a:

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:y'', x'')
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

asi que x'' = [5] y y'' = []:

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:[], [5])
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

asi que x' = [5] y y' = [2]:

(1:y, x)
    where (x, y) = (4:[5], [2])
          (x', y') = (2:[], [5])
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

asi que x = [4, 5] y y = [2] así que eventualmente obtenemos:

(1:[2], [4,5])
    where (x, y) = (4:[5], [2])
          (x', y') = (2:[], [5])
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

entonces el resultado es el esperado ([1,2], [4,5]).

Aproximadamente,

foldr (a ~(x,y) -> (a:y,x)) ([],[]) [a,b,c,d,e]
=
let g a ~(x,y) = (a:y,x) in
g a $ g b $ g c $ g d $ g e ([],[])
=
g a $ g b $ g c $ g d $ ([e],[])
=
g a $ g b $ g c $ ([d],[e])
=
g a $ g b $ ([c,e],[d])
=
g a $ ([b,d],[c,e])
=
([a,c,e],[b,d])

Pero verdaderamente

foldr (a ~(x,y) -> (a:y,x)) ([],[]) [a,b,c,d,e]
=
let g a ~(x,y) = (a:y,x) in
g a $ foldr g ([],[]) [b,c,d,e]
=
(a:y,x) where 
    (x,y) = foldr g ([],[]) [b,c,d,e]
=
(a:y,x) where 
    (x,y) = (b:y2,x2) where
                 (x2,y2) = foldr g ([],[]) [c,d,e]
=
(a:y,x) where 
    (x,y) = (b:y2,x2) where
                 (x2,y2) = (c:y3,x3) where
                                (x3,y3) = (d:y4,x4) where
                                               (x4,y4) = (e:y5,x5) where
                                                              (x5,y5) = ([],[])

que es forzado en el De arriba hacia abajo manera por acceso (si y cuando), desarrollándose progresivamente como, por ejemplo,

=
(a:x2,b:y2) where 
                 (x2,y2) = (c:y3,x3) where
                                (x3,y3) = (d:y4,x4) where
                                               (x4,y4) = (e:y5,x5) where
                                                              (x5,y5) = ([],[])
=
(a:c:y3,b:x3) where 
                                (x3,y3) = (d:y4,x4) where
                                               (x4,y4) = (e:y5,x5) where
                                                              (x5,y5) = ([],[])
=
(a:c:x4,b:d:y4) where 
                                               (x4,y4) = (e:y5,x5) where
                                                              (x5,y5) = ([],[])
=
(a:c:e:y5,b:d:x5) where 
                                                              (x5,y5) = ([],[])
=
(a:c:e:[],b:d:[]) 

pero podría ser que el forzamiento se haga en un orden diferente, dependiendo de cómo se llame, p. ej.

print . (!!1) . snd $ foldr (a ~(x,y) -> (a:y,x)) ([],[]) [a,b,c,d,e]
print . (!!2) . fst $ foldr (a ~(x,y) -> (a:y,x)) ([],[]) [a,b,c,d,e]

etc.

---

editar: para abordar las preguntas sobre el patrón perezoso, se hace para la pereza adecuada de la función resultante:

• foldr con la función de combinación que es estricto en su segundo argumento, codifica recursividad, cual es de abajo hacia arriba. El resultado del procesamiento recursivo del resto de la lista se construye primero, y la parte principal del resultado se combina con eso, después.

• foldr con la función de combinación que es perezoso en su segundo argumento, codifica corecursion, cual es De arriba hacia abajo. La parte principal del valor resultante se construye primero y el resto se completa más tarde. Es muy reminiscente de cola recursividad módulo contras, en Prolog y en otros lugares. La evaluación perezosa como concepto vino de “CONS no debe evaluar sus argumentos “; TRMC no evalúa la segundo argumento al constructor hasta más tarde, que es lo que realmente importa.

---

---

Utiliza Nuestro Buscador