#haskell
#haskell
Вопрос:
Функция, которую я создал, showTree
, берет дерево Хаффмана с узлами и листьями и «аккуратно» печатает его в оболочке.
Вот функция:
showTree :: Tree -> String
showTree (Leaf c i) = [c] show i
showTree (Node v t1 t2) =
left "n" middle right
where middle = replicate (heightTree (Node v t1 t2)) ' ' replicate (heightTree (Node v t1 t2)) ' ' replicate (heightTree (Node v t1 t2)) ' ' show v
left = showTree t1
right = showTree t2
На данный момент он печатает узлы и листья непосредственно рядом друг с другом. Результат в конечном итоге выглядит следующим образом:
i2
4l2
8a1
2g1
4h2
21r2
5t1
3n1
2s1
13 4
8e4
Первое число, которое вы видите в каждом элементе, — это номер узла, за которым следует конечный символ и целое число. Я пытаюсь сделать так, чтобы это выглядело так:
' '(4)
8
i(2)
4
l(2)
13
a(1)
2
t(1)
5
g(1)
2
s(1)
3
n(1)
21
e(4)
8
h(2)
4
r(2)
или что-то в этом роде. Я в основном просто пытаюсь понять, как отображать листья только в конце дерева, где они принадлежат.
Ответ №1:
Для этого можно использовать boxes
библиотеку.
showTree :: Tree -> Box
showTree (Leaf c i) = text $ concat [[c], "(", show i, ")"]
showTree (Node v t1 t2) = vcat right
[ moveLeft 6 (go t1)
, text (show v)
, moveLeft 6 (go t2)
]
В ghci:
> printBox $ showTree (Node 21 (Node 13 (Node 8 (Leaf ' ' 4) (Node 4 (Leaf 'i' 2) (Leaf 'l' 2))) (Node 5 (Node 2 (Leaf 'a' 1) (Leaf 't' 1)) (Node 3 (Node 2 (Leaf 'g' 1) (Leaf 's' 1)) (Leaf 'n' 1)))) (Node 8 (Leaf 'e' 4) (Node 4 (Leaf 'h' 2) (Leaf 'r' 2)))
(4)
8
i(2)
4
l(2)
13
a(1)
2
t(1)
5
g(1)
2
s(1)
3
n(1)
21
e(4)
8
h(2)
4
r(2)