Построение дерева по определенному списку

Question

Каков наилучший способ построить дерево из списка? Мне интересно найти функциональный способ решения этой проблемы. Какие пакеты и модули могут вам помочь?

Этот вопрос касается фактического хранения исходной структуры в дереве, не только отображения его как дерева.

Первоначальная структура:

[[1, 1, 1, 0.5], 
[1, 1, 2, 0.5], 
[1, 1, 3, 0.5], 
[1, 1, 4, 0.5], 
[1, 1, 5, 0.5], 
[1, 2, 1, 0.5], 
[1, 2, 2, 0.5], 
[1, 2, 3, 0.5], 
[1, 2, 4, 0.5], 
[1, 2, 5, 0.5]] 

Результат (набран руками):

Node 1 
    Node 1 
     Node 1 
      Node 0.5 
     Node 2 
      Node 0.5 
     Node 3 
      Node 0.5 
     Node 4 
      Node 0.5 
     Node 5 
      Node 0.5 
    Node 2 
     Node 1 
      Node 0.5 
     Node 2 
      Node 0.5 
     Node 3 
      Node 0.5 
     Node 4 
      Node 0.5 
     Node 5 
      Node 0.5 

Спасибо!

Answer 1

Определить некоторую структуру дерева

data T a = T a [T a] deriving Show 

и вставить каждую строку в

insert :: Eq a => [T a] -> [a] -> [T a] 
insert ts [] = ts 
insert [] (x:xs) = [T x $ insert [] xs] 
insert (t@(T n ns):ts) xss@(x:xs) 
    | n == x = (T n (insert ns xs)):ts 
    | otherwise = t: insert ts xss 

многих строк дерева

fromList :: Eq a => [[a]] -> [T a] 
fromList = foldl insert [] 

для печати

showTree :: Show a => [T a] -> [String] 
showTree ts = concat [ ("Node " ++ show n): map (" "++) (showTree ns) | T n ns <- ts] 

Пример

main = do 
    putStrLn $ unlines $ showTree $ fromList 
     [[1, 1, 1, 0.5], 
     [1, 1, 2, 0.5], 
     [1, 1, 3, 0.5], 
     [1, 1, 4, 0.5], 
     [1, 1, 5, 0.5], 
     [1, 2, 1, 0.5], 
     [1, 2, 2, 0.5], 
     [1, 2, 3, 0.5], 
     [1, 2, 4, 0.5], 
     [1, 2, 5, 0.5]] 

результате

Node 1.0 
    Node 1.0 
    Node 1.0 
     Node 0.5 
    Node 2.0 
     Node 0.5 
    Node 3.0 
     Node 0.5 
    Node 4.0 
     Node 0.5 
    Node 5.0 
     Node 0.5 
    Node 2.0 
    Node 1.0 
     Node 0.5 
    Node 2.0 
     Node 0.5 
    Node 3.0 
     Node 0.5 
    Node 4.0 
     Node 0.5 
    Node 5.0 
     Node 0.5 

Answer 2

Это иногда называют розы дерево, Data.Tree из упаковки контейнеров (который поставляется с GHC) обеспечивают определение типа и некоторые инструменты для обработки тех (очень простой, но поскольку у вас их уже есть ...).

Вы можете выполнить задание, вставив несколько раз каждый путь, но это не будет использовать структуру вашего списка. Если вам гарантировано, что он будет отсортирован, вы можете напрямую сгенерировать Дерево (или, скорее, Лес, поскольку нет гарантии, что все ваши подсписчики имеют одну и ту же голову), группируя подсписку с помощью аналогичных головок, затем рекурсивно создавая подлесы из хвостов:

fromSortedList :: (Eq a) => [[a]] -> Forest a 
fromSortedList [] = [] 
fromSortedList xs = concatMap fromOneGroup . groupBy eq $ xs 
    where 
    eq (x:_) (y:_) = x == y 
    eq _  _  = False 
    fromOneGroup ([] : _) = [] 
    fromOneGroup xs  = [Node (head . head $ xs) (fromSortedList . map tail $ xs)] 

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