我需要创建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使用list 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

看起来我们已经完成了!一些重要的经验:

• 首先考虑小案例,然后从那里开始构建.
• 列表monad对于需要生成所有事物组合的代码非常有用.
• 您不必一次完成所有事情.单独处理列表拆分使代码比其他方式更简单.