haskell - 生成所有可能的树

给定以下数据类型定义：

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

最佳答案

这是一个不错的把戏，让人想起标准的斐波那契数字把戏。我们将建立一个惰性列表；列表的每个成员将是具有给定节点数的所有树的列表。只有一棵没有节点的树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]

...这确实是前十个Catalan numbers，所以我们可能做对了！