Nuestros programadores estrellas han agotado sus provisiones de café, investigando todo el tiempo por la respuesta, hasta que Noé halló el arreglo en Bitbucket por lo tanto en este momento la compartimos aquí.
Solución:
Podrías estudiar el drawTree función en la base Data.Tree módulo. Importarlo descaradamente te daría algo como esto:
import Data.Tree hiding (Tree )
data Tree a b = Branch b (Tree a b) (Tree a b)
| Leaf a deriving (Eq,Ord,Show)
toDataTree (Leaf a) = Node a []
toDataTree (Branch b cs ds) = Node b [toDataTree cs, toDataTree ds]
d = Branch "1" (Branch "11" (Leaf "111") (Leaf "112"))
(Branch "12" (Leaf "121") (Leaf "122"))
e = toDataTree d
f = putStrLn $ drawTree e
+- 111
Usando el enlace del aplicativo al Data.Tree fuente se me ocurrió esto. Quería escribir la mía propia para poder aprender más sobre ella. los drawTree el método en la fuente está generalizado para trabajar con nodos con varios hijos; el mío es solo para árboles binarios.
Nota: la definición de mi árbol es un poco diferente a la de los OP. No entiendo muy bien lo que a para el que se usa el parámetro de tipo, pero el enfoque debe ser el mismo
data Tree a
= Branch (Tree a) a (Tree a)
| Leaf
prettyprint (Leaf)
= "Empty root."
-- unlines concats a list with newlines
prettyprint (Branch left node right) = unlines (prettyprint_helper (Branch left node right n h))
prettyprint_helper (Branch left node right)
= (show node) : (prettyprint_subtree left right)
where
prettyprint_subtree left right =
((pad "+- " "| ") (prettyprint_helper right))
++ ((pad "`- " " ") (prettyprint_helper left))
pad first rest = zipWith (++) (first : repeat rest)
prettyprint_helper (Leaf)
= []
Que produce un árbol como
4
+- 8
| +- 9
| | +- 10
| `- 6
| +- 7
| `- 5
`- 2
+- 3
`- 1
Solo quería explicar cómo pad La función funciona, ya que eso fue lo más difícil de seguir para mí (llamado shift en la fuente).
Primeramente, zipWith aplica una función (primer argumento) para “unir” dos listas. zipWith (+) [1, 2, 3] [4, 5, 6] regreso [5, 7, 9]. Se detiene cuando una de las listas está vacía. zipWith aplicado a solo una lista devuelve una función que se puede aplicar para comprimir una segunda lista (creo que esto se conoce como función de curado). Aquí hay una versión más simple del pad función:
> let pad = zipWith (++) (repeat " ")
> :type pad
pad :: [[Char]] -> [[Char]]
> pad ["1", "2", "3"]
[" 1", " 2", " 3"]
Aviso: 1. Una de las listas es infinita (repeat " "), pero se detiene cuando una de las listas está vacía 2. zipWith solo toma una función y una lista. pad es entonces una función que toma una lista de la lista de caracteres / cadenas y devuelve la lista comprimida de la lista de caracteres / cadenas. Así que aplica pad en una sola lista para cerrarla con la primera
Ahora veamos
prettyprint_subtree left right =
((pad "+- " "| ") (prettyprint_helper left))
++ ((pad "`- " " ") (prettyprint_helper right))
(pad "+- " "| ") crea una lista infinita como ["+- ", "| ", "| ", "| ", ...]. (prettyprint_helper right) crea la lista de líneas que representa el subárbol de la derecha, comenzando con el nodo raíz de la derecha. Pero todo ese árbol debe desplazarse hacia la derecha; lo hacemos cerrándolo con el relleno. Usamos una lista infinita porque no sabemos qué tan grande es el subárbol; siempre habrá suficiente "| "s para rellenar las líneas adicionales (esto también funciona debido a la evaluación diferida). Tenga en cuenta que la primera línea; es decir, el subárbol-raíz-nodo, se rellena con "+- " en cambio, la “notación” para un nodo derecho.
El lado izquierdo es prácticamente el mismo. La notación para un nodo izquierdo es "`- ". La única otra diferencia es el acolchado; " " en lugar de "| ". Entonces, ¿por qué los nodos izquierdos no necesitan las “ramas”? Bueno, puedes pensar en ello como el detrás los nodos de la derecha (se añade el relleno; a la izquierda) van a los nodos de la izquierda a continuación. Necesita el relleno detrás de la derecha para conectar el nodo / subárbol izquierdo al nodo principal. No hay nada detrás del lado izquierdo de un árbol, excepto posiblemente el árbol padre. Lo que me lleva a mi último punto; cada subárbol, representado como una lista de líneas en el prettyprint_helper función, obtiene un nivel adicional de relleno de cada árbol padre. Creo que se ilustra mejor con un ejemplo.
Al crear el árbol de arriba (tenga en cuenta, no sé exactamente el orden de ejecución, especialmente con la evaluación diferida, pero esto es solo para ayudar a visualizar por qué funciona):
Digamos que recurrimos a 10. Bueno, el subárbol de la izquierda y el subárbol de la derecha están vacíos, así que prettyprint_helper (Branch Leaf 10 Leaf) devoluciones ["10"].
Ahora estamos a la altura 9. Su subárbol es: "9" : ([] ++ ((pad "+- " "| ") [10])) (sin lado izquierdo), o "9" : ["+- 10"], o:
9
+- 10
Ahora estamos a la altura 8. ((pad "+- " "| ") (prettyprint_helper right)) crea:
+- 9
| +- 10
Puede rastrearlo usted mismo, pero el lado izquierdo es:
6
+- 7
`- 5
¿Qué almohadillas para (primer elemento "`- ", descansar " "):
`- 6
+- 7
`- 5
Entonces, en total para 8, que es el lado izquierdo adjunto al lado derecho, tenemos:
8
+- 9
| +- 10
`- 6
+- 7
`- 5
Si damos un paso hacia arriba, esto 8 el subárbol está relleno para el 4 árbol, y nuevamente puede rastrear a través del otro lado para verificar que funciona. Usted obtiene
+- 8
| +- 9
| | +- 10
| `- 6
| +- 7
| `- 5
Y el resultado final es el anterior. Recuerde, a lo largo de este proceso, el árbol se representa como una lista de líneas. Solo al final se junta con unlines. Quizás mis dibujos sean engañosos porque puede parecer que los subárboles se pasan como cadenas de varias líneas. Una vez que comprenda esto, es muy fácil agregar la rama adicional ("|") entre los nodos izquierdo y derecho como en Data.Tree‘s drawTree función. Dejaré que lo averigües 🙂
Mis disculpas si esto es excesivo; Fue bastante difícil para mí entender desde la fuente como principiante, y esto fue un gran salto para mí. Espero que ayude a alguien más a intentar resolver este problema.
Acuérdate de que te brindamos la opción de agregar una reseña si te ayudó.