haskell - 我需要创建 haskell 函数，它返回所有可能的二叉树，给定一个整数列表

Question

正如标题所说，我需要这个:

    getAllTrees :: [Int] -> [Tree Int]
    getAllTrees xs = undefined

树在哪里

    data Tree x 
      = Null
      | Leaf x
      | Node (Tree x) x (Tree x)

我将不胜感激任何帮助，即使是最小的线索:)
谢谢

Answer 1

我通常发现使用 list monad 来解决这些类型的问题最容易。我们可以定义 getAllTrees推理如下:

唯一的零项树是 Null :

getAllTrees [] = return Null

也只有一个元素的一棵树，即 Leaf :

getAllTrees [x] = return $ Leaf x

当我们有多个元素时，我们可以以所有可能的方式拆分列表以确定我们应该如何分支，然后从每个列表递归生成子树。假设我们有一个函数 splits :: [a] -> [([a], [a])]返回拆分列表的所有方式，例如:

> splits [1..3]
[([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])]

然后我们可以定义 getAllTrees 的最终情况通过使用列表 monad。这使我们能够编写看起来像我们只关注一种情况的代码，而 monad 将为我们提供所有组合。

getAllTrees xs = do
  (left, x : right) <- splits xs
  Node <$> getAllTrees left <*> pure x <*> getAllTrees right

第一行分割输入列表，并将第二部分的第一项作为中间元素。第二部分为空的情况与模式不匹配，因此它被丢弃，因为这是列表 monad 处理模式匹配失败的方式。

第二行使用应用语法表示我们希望结果是一个节点列表，由来自 left 的子树的所有组合组成。列表，固定中间元素 x ，以及来自 right 的所有子树列表。

剩下的就是实现 splits .看上面的例子，很容易看出我们可以取 inits和 tails列表和 zip他们在一起:

splits xs = zip (inits xs) (tails xs)

是时候在解释器中快速检查完整性了:

> mapM_ print $ getAllTrees [1..3]
Node Null 1 (Node Null 2 (Leaf 3))
Node Null 1 (Node (Leaf 2) 3 Null)
Node (Leaf 1) 2 (Leaf 3)
Node (Node Null 1 (Leaf 2)) 3 Null
Node (Node (Leaf 1) 2 Null) 3 Null
> length $ getAllTrees [1..5]
42

看起来我们已经完成了!一些关键教训:

尝试先考虑小案例，然后从那里开始积累。

list monad 对于需要生成所有事物组合的代码很有用。

你不必一次做所有的事情。单独处理列表拆分使代码比其他方式简单得多。