Как построить дерево сбоку и вниз?

Question

Как я могу построить дерево вниз и горизонтально?

У меня сейчас есть дерево:

data Tree a = Node a [Tree a]

Затем у меня есть корень Int и список [Int]

1 and [2,3,4]

Я хочу построитьдерево как

       1
    /  |  \
   2   3   4
  /\  / \  /\
 3  4 2 4 2  3
 |  | | | |  |
 4  3 4 2 3  2 

В Haskell это выглядит так:

Node 1 [Node 2 [Node 3 [Node 4 []],Node 4[Node 3 []]], Node 3 [Node 2 [Node 4 []], 
Node 4 [Node 2 []]], Node 4 [Node 2 [Node 3 []], Node 3 [Node 2 []]]]

Вот что я пробовал: Этот код вырастает мое дерево вниз

down :: Int -> [Int] -> Tree Int
down y [] = Node y []
down y (x:xs) = Node y [down x xs]

Этот кодрастёт моё дерево сбоку

side :: Int -> [Int] -> Tree Int
side y [] = Node y []
side y x = Node y $ map (\x -> Node x []) y

Теперь у меня проблемы с соединением, чтобы получить решение выше. Любая помощь приветствуется

Answer 1

Мы можем ввести вспомогательную функцию pick, которая будет генерировать список из двух кортежей с выбранным элементом и возвращать оставшийся список. Мы можем реализовать это с помощью списка различий, но простая, менее эффективная реализация:

import Data.List(tails, inits)

pick :: [a] -> [(a, [a])]
pick vs = [(x, ws ++ xs) | (ws, (x:xs)) <- zip (inits vs) (tails vs) ]

Затем мы получаем:

Prelude Data.List> pick [2,3,4]
[(2,[3,4]),(3,[2,4]),(4,[2,3])]

Теперь мы можем изменить вашу down функцию:

down :: a -> [a] -> Tree a
down y = Node y . map (uncurry down) . pick

Для данных данного примера мы получим:

Prelude Data.List> down 1 [2,3,4]
Node 1 [Node 2 [Node 3 [Node 4 []],Node 4 [Node 3 []]],Node 3 [Node 2 [Node 4 []],Node 4 [Node 2 []]],Node 4 [Node 2 [Node 3 []],Node 3 [Node 2 []]]]