生成所有可能的树

Question

给定以下数据类型定义:

data FormTree = Empty | Node FormTree FormTree deriving Show

我想编写一个函数,它生成一个无限列表,其中包含按长度排序的所有可能的树,例如节点的数量.

下面的代码几乎可以满足我的需要,但它只是通过每次插入额外的节点来降低右侧的树,但我需要它在两边之间交替.

allPossibleTrees :: [FormTree]
allPossibleTrees = Empty : [Node x y | x <- recursive, y <- recursive]
    where recursive = allPossibleTrees

执行

take 5 allPossibleTrees

得到:

[Empty,Node Empty Empty,Node Empty (Node Empty Empty),Node Empty (Node Empty (Nodes Empty Empty)),Node Empty (Node Empty (Node Empty (Node Empty Empty)))]

但它应该是这样的:

[Empty,Node Empty Empty,Node (Node Empty Empty) Empty,Node Empty (Node Empty Empty),Node (Node Empty Empty) (Node Empty Empty)]

Answer 1

这是一个很好的技巧,让人联想到标准的Fibonacci数字技巧.我们将建立一个懒惰的列表; 列表的每个成员将是具有给定节点数的所有树的列表.只有一棵树没有节点,Empty这将作为我们的基础案例.要构建所有的树n节点,我们假设我们已经知道如何建立与树木0,1,2,...,n-1节点.然后,我们将非确定性地选择那些总和n-1和Node顶部的配对.

在代码中:

import Control.Monad
import Data.List

sizes :: [[FormTree]]
sizes = [Empty] : (map go . drop 1 . inits) sizes where
    go smaller = do
      (ls, rs) <- zip smaller (reverse smaller)
      liftM2 Node ls rs

然后我们可以简单地定义allPossibleTrees = concat sizes是否需要.前几个条目:

*Main> mapM_ print (take 4 sizes)
[Empty]
[Node Empty Empty]
[Node Empty (Node Empty Empty),Node (Node Empty Empty) Empty]
[Node Empty (Node Empty (Node Empty Empty)),Node Empty (Node (Node Empty Empty) Empty),Node (Node Empty Empty) (Node Empty Empty),Node (Node Empty (Node Empty Empty)) Empty,Node (Node (Node Empty Empty) Empty) Empty]

我们可以快速进行健全检查:

*Main> take 10 (map length sizes)
[1,1,2,5,14,42,132,429,1430,4862]

......这确实是前10个加泰罗尼亚数字,所以我们可能做对了!