Haskell дисплей Дерево без Data.Tree или выводе формулы (шоу)

Question

Привет ребята У меня возникли проблемы с моей, например, чтобы показать дерево в Haskell: вот мой код:

data Tree a b = Branch b (Tree a b) (Tree a b) 
      | Leaf a 
instance (Show a, Show b) =>Show (Tree a b) where 
show (Leaf x) = " "++show x ++"\n" 
show (Branch val l r) = show val ++ "\n" ++" " ++ show l ++ " " ++ show r 

вот мой тест и вывод (что неверно):

Branch "<" (Branch "<" (Leaf 'a') (Leaf 'c')) (Branch "<" (Leaf 'g') (Branch  "<" (Leaf 'n') (Leaf 'y')))) 
"<" 
    "<" 
    'a' 
    'c' 
    "<" 
    'g' 
    "<" 
    'n' 
    'y' 

правый выход

"<" 
    "<" 
    'a' 
    'c' 
    "<" 
    'g' 
    "<" 
     'n' 
     'y' 

любая помощь будет здорово!

Answer 1

Ваша функция отображения не имеет способа узнать, как глубоко отступать каждая строка. Предоставление пространства вашим поддеревьям не будет работать, потому что они обычно имеют более одной строки.

Вам нужно определить вспомогательную функцию, которая принимает отступы в качестве параметра:

indent n x = concat (replicate n " ") ++ show x ++ "\n" 

f n (Leaf x) = indent n x 
f n (Branch val l r) = indent n val ++ f (n+1) l ++ f (n+1) r 

instance (Show a, Show b) => Show (Tree a b) where 
    show tree = f 0 tree 

Answer 2

Рассмотрим следующий пример:

putStrLn ("First line" ++ " " ++ "\n" ++ "Second line") 

Выход

First line 
Second line 

, потому что символ новой строки не содержит отступов. Вам нужно найти способ сообщить show, какой размер отступа требуется для каждого элемента, который вы хотите распечатать.

Answer 3

^{Примечание: Это сообщение написано грамотным Haskell. Скопируйте его в свой любимый редактор, сохраните его как Tree.lhs или аналогичный и загрузите в GHCi.}

Давайте попробуем немного другой подход. Вместо того чтобы показывать дерево в виде одной строки, мы создаем линии нашей строки:

> data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a 

> instance (Show a, Show b) => Show (Tree a b) where 
> show tree = magic (go tree) 
>  where 
>  go :: (Show a, Show b) => Tree a b -> [String] 

Не беспокоиться еще о magic, это будет иметь тип magic :: [String] -> String. Прежде всего сосредоточимся на go. Если мы хотим показать одну Leaf, мы должны только касаться одного значения:

>  go (Leaf v)  = [show v] 

Теперь о филиалах и их отступа. Мы можем показать значение, как и в случае Leaf:

>  go (Branch v l r) = show v 

, но мы должны убедиться, что фактические ветви имеют правильное количество пробелов впереди. Мы используем функцию (пока не определено) называется indent:

>      : indent (go l ++ go r) 

Теперь у нас есть почти все на месте: если indent делает то, что предполагает его название, он собирается отступа все строки в [String] возвращенного go l ++ go r на одно место. Поэтому ветви дерева всегда будут иметь еще одно пространство спереди, как сам корень.Все, что не хватает теперь indent и magic:

>  indent :: [String] -> [String] 
>  indent = map (' ':) 

Это было довольно легко. Конечно, вы можете обменять (' ':) с чем-то еще.

Это работа magic, чтобы взять все струны и приклеить их вместе. Так как вы хотите, чтобы отступы всего дерева на одном пространстве, давайте использовать indent в последний раз:

>  magic = unlines . indent 

И это все. Вот весь код для лучшего обзора:

instance (Show a, Show b) => Show (Tree a b) where 
    show tree = magic (go tree) 
    where 
     go (Leaf v)  = [show v] 
     go (Branch v l r) = show v : indent (go l ++ go r) 
     indent   = map (' ':) 
     magic    = unlines . indent 

Хорошая часть об этой технологии является то, что мы никогда не должны использовать явные уровни или указать количество пространств где-то. Мы можем просто прогуляться по дереву, создать наш [String] и иметь magic и indent сделать остальное для нас.

Answer 4

Тип Tree меня раздражает, потому что это монада, но не может быть Monad. Позвольте мне исправить это для вас, перевернув аргументы типа:

data Tree b a = Branch b (Tree a b) (Tree a b) 
       | Leaf a 

display' :: (Show a, Show b) => String -> Tree b a -> String -> String 
display' prefix (Leaf a) = 
    (prefix ++) . shows a . ('\n' :) 
display' prefix (Branch v l r) = 
    (prefix ++) . shows v . ('\n' :) . display' prefix' l . display' prefix' r 
    where prefix' = ' ' : prefix 

display :: (Show a, Show b) => Tree b a -> String 
display t = display' ' ' t ""