Попытка распечатать дерево кода Хаффмана в haskell

#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)