如何横向和向下建造一棵树？

debugcn 发表于 Dev

呼叫25

我怎样才能水平向下建造一棵树？

我目前有一棵树：

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

现在，我很难将其拼凑在一起以获得上述解决方案。任何帮助表示赞赏

威廉·范昂塞姆

我们可以引入一个辅助函数pick，该函数将生成一个带有选择的项目的2元组列表，并返回剩余的列表。我们可以使用差异列表来实现，但是一个简单，效率较低的实现是：

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 []]]]

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。