2012-05-15 18 views
12

Estaba pensando en aplanar un árbol binario en una lista, para el último procesamiento.Haskell: Acoplar árbol binario

Primero pensé en usar (++) para unirme a las ramas izquierda y derecha, pero luego pensé en el peor caso que tomaría O(n^2) vez.

Luego pensé en construir la lista al revés, usando (:) para anexar al frente en tiempo lineal. Sin embargo, entonces pensé que si envío esta lista a una función de plegado, tiene que esperar hasta que se cruce todo el árbol antes de que pueda comenzar a plegarse, y por lo tanto no puede usar list fusion.

entonces se le ocurrió la following:

data Tree a = Node a (Tree a) (Tree a) | Tip 

flatten :: Tree a -> [a] 
flatten x = (flatten' x) [] 

flatten' :: Tree a -> [a] -> [a] 
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l))) 
flatten' Tip l = l 

main = 
    putStrLn $ show $ flatten $ 
    (Node 2 (Node 1 Tip Tip) (Node 4 (Node 3 Tip Tip) Tip)) 

es que esto funciona en O(n) tiempo, tomar "espacio de pila" no es más que proporcional a la mayor profundidad del árbol y puede que estar condensado con un consumo de función (es decir, lista intermedia eliminada)? ¿Es esta la forma "correcta" de aplanar un árbol?

+1

http://hackage.haskell.org/packages/archive/containers/latest/doc/html/src/Data-Map-Base.html#foldl –

+0

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. –

Respuesta

12

No sé mucho sobre la fusión, pero creo que las funciones recursivas en general no se pueden fusionar. Pero recuerde que cuando se trata de listas en Haskell, las listas intermedias generalmente no existen como un todo, todas a la vez: usted sabrá el principio y no habrá calculado el final, y luego, tirará el principio y sabrá el final (en tantos pasos como haya elementos de la lista). Esto no es fusión, esto es más como "transmitir buena conducta", y significa que los requisitos de espacio son mejores si la salida se consume de forma incremental.

De todos modos, sí, creo que esta es la mejor manera de aplanar un árbol. Cuando el resultado de un algoritmo es una lista pero, de lo contrario, la lista no se examina y hay una concatenación en curso, entonces difference lists (DList s) suelen ser la mejor opción. Representan una lista como una "función de preinicio", que elimina la necesidad de un recorrido transversal cuando se agrega, ya que agregar es solo la composición de la función.

type DList a = [a] -> [a] 

fromList :: [a] -> DList a 
fromList xs = \l -> xs ++ l 

append :: DList a -> DList a -> DList a 
append xs ys = xs . ys 

toList :: DList a -> [a] 
toList xs = xs [] 

Esos son los elementos esenciales de la ejecución, el resto se pueden derivar de eso. El algoritmo de aplanamiento ingenua en DList s es:

flatten :: Tree a -> DList a 
flatten (Node x left right) = flatten left `append` fromList [x] `append` flatten right 
flatten Tip = fromList [] 

Vamos a hacer un poco de expansión. Comience con la segunda ecuación:

flatten Tip = fromList [] 
      = \l -> [] ++ l 
      = \l -> l 
flatten Tip l = l 

¿A dónde va esto? Ahora la primera ecuación:

flatten (Node x left right) 
    = flatten left `append` fromList [x] `append` flatten right 
    = flatten left . fromList [x] . flatten right 
    = flatten left . (\l -> [x] ++ l) . flatten right 
    = flatten left . (x:) . flatten right 
flatten (Node x) left right l 
    = (flatten left . (x:) . flatten right) l 
    = flatten left ((x:) (flatten right l)) 
    = flatten left (x : flatten right l) 

que muestra cómo la formulación DList es igual a la función!

flatten' :: Tree a -> [a] -> [a] 
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l))) 
flatten' Tip l = l 

no tengo ninguna prueba de por qué DList es mejor que otros enfoques (y en última instancia, depende de cómo se está consumiendo su salida), pero DList es la forma canónica de hacerlo de manera eficiente, y que es Qué has hecho.

+0

Para ampliar los aspectos más teóricos de DLists, hay [página en la wiki de Haskell] (http://www.haskell.org/haskellwiki/Difference_list) sobre DLists (no es muy claro), pero la idea básica es usted evite tener que pasar por las aplicaciones anidadas O (n) de '(++)' solo para obtener el primer elemento, en su lugar puede tomarlo directamente de la función más externa (la aplicación más a la izquierda de '(.)') . (Nota: este es un resumen amplio, la realidad es un poco más sutil que esto.) – huon

2

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 flattenhere 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.

+3

'flatten'' no es cola recursiva. hay 2 llamadas recursivas – newacct