flatten'
es cola recursiva, por lo que no debería ocupar ningún espacio de pila. Sin embargo, caminará por el lado izquierdo del árbol, escupiendo un montón de trozos en el montón.Si se invoca en su ejemplo de árbol, y reducirla a WHNF, usted debe conseguir algo que se parece a esto:
:
/\
1 flatten' Tip :
/\
2 flatten' (Node 4) []
/ \
(Node 3) Tip
/ \
Tip Tip
El algoritmo es O(N)
, pero tiene que examinar la Tip
s, así como las Node
s .
Parece ser la manera más eficiente de aplanar su árbol en orden. El módulo Data.Tree
tiene una función flatten
here que hace más o menos lo mismo, excepto que prefiere un recorrido de pre-pedido.
Actualización:
En un motor de reducción de grafos, el flatten
en main
generará un gráfico como este:
@
/\
@ []
/\
/ \
/ \
flatten' Node 2
/ \
/ \
/ \
Node 1 Node 4
/ \ / \
Tip Tip/ \
/ \
Node 3 Tip
/ \
Tip Tip
Con el fin de reducir esto a WHNF, el motor de reducción de grafos se desenrolle el lomo, empujando el []
y el Node 2
en la pila. A continuación, invocar la función flatten'
, que volverá a escribir el gráfico para esto:
@
/\
/ \
/ \
@ :
/\ /\
/ \ 2 \
/ \ \
flatten' Node 1 \
/ \ \
Tip Tip @
/\
@ []
/\
/ \
/ \
flatten' Node 4
/ \
/ \
/ \
Node 3 Tip
/ \
Tip Tip
Y hará estallar los dos argumentos de la pila. El nodo raíz aún no está en WHNF, por lo que el motor de reducción de gráficos desenrollará el lomo, empujando el 2:...
y el Node 1
en la pila. A continuación, invocar la función flatten'
, que volverá a escribir el gráfico para esto:
@
/\
/ \
/ \
@ :
/\ /\
/ \ 1 \
/ \ \
flatten' Tip @
/\
/ \
/ :
@ /\
/\ 2 \
/Tip @
/ /\
flatten' @ []
/\
/ \
/ \
flatten' Node 4
/ \
/ \
/ \
Node 3 Tip
/ \
Tip Tip
Y hará estallar los dos argumentos de la pila. El nodo raíz es todavía no en WHNF, por lo que el motor de reducción de gráficos desenrollará el lomo, empujando el 1:...
y el Tip
en la pila. A continuación, invocar la función flatten'
, que volverá a escribir el gráfico para esto:
:
/\
1 \
\
@
/\
/ \
/ :
@ /\
/\ 2 \
/Tip @
/ /\
flatten' @ []
/\
/ \
/ \
flatten' Node 4
/ \
/ \
/ \
Node 3 Tip
/ \
Tip Tip
Y hará estallar los dos argumentos de la pila. Ahora estamos en WHNF, después de haber consumido un máximo de dos entradas de pila (suponiendo que los nodos Tree
no eran thunks que requirieran espacio de pila adicional para evaluar).
Por lo tanto, flatten'
es tail-recursive. Se reemplaza a sí mismo sin tener que evaluar redex anidados adicionales. El segundo flatten'
sigue siendo un thunk en el montón, no en la pila.
http://hackage.haskell.org/packages/archive/containers/latest/doc/html/src/Data-Map-Base.html#foldl –
Como señala luqui, esta es una técnica de lista de diferencias. [este] (http://stackoverflow.com/a/10584256/849891) y [este] (http://stackoverflow.com/a/9550430/849891) están relacionados también. –