Haskell allTrees生成存储叶数二叉树结果异常求解

你的初始实现错误源于列表Applicative实例的求值顺序和递归定义的惰性求值特性：branch allTrees allTrees会优先递归生成所有左偏斜的链式二叉树，永远不会枚举左子树为非单叶节点、右子树为更小结构的组合，因此输出全是沿左子树无限延伸的单链，和预期的全量枚举结果不符。

要枚举所有存储叶子数的二叉树，核心是按叶子节点总数从小到大分组生成：

• 叶子数为1的树只有1种，即叶子节点本身
• 叶子数为n（n≥2）的树必然是分支节点：左子树叶子数k可取1到n-1，对应右子树叶子数为n-k，将所有合法的左、右子树两两组合，就能得到该叶子数下的全部二叉树
• 将所有叶子数对应的树列表按顺序拼接，就得到无穷递增的allTrees列表

你提到的foldM更适合带状态累积的一元计算场景，这个问题不需要使用，用列表推导即可直接实现。

data BTree = L | B BTree BTree
    deriving (Eq, Ord, Show)

data SpecTree = S Integer BTree
    deriving (Eq, Ord, Show)

leafNode :: SpecTree
leafNode = S 1 L

branch :: SpecTree -> SpecTree -> SpecTree
branch (S size1 sub1) (S size2 sub2) = S (size1 + size2) (B sub1 sub2)

-- 生成指定叶子数的所有合法二叉树
treesOfSize :: Integer -> [SpecTree]
treesOfSize 1 = [leafNode]
treesOfSize n =
  [ branch l r
  | k <- [1 .. n-1]  -- 枚举左子树所有可能的叶子数
  , l <- treesOfSize k
  , r <- treesOfSize (n - k)
  ]

-- 按叶子数从小到大拼接所有树，得到无穷列表
allTrees :: [SpecTree]
allTrees = concatMap treesOfSize [1..]

执行take 9 allTrees会得到和你预期完全一致的输出：

[S 1 L,S 2 (B L L),S 3 (B L (B L L)),S 3 (B (B L L) L),S 4 (B L (B L (B L L))),S 4 (B L (B (B L L) L)),S 4 (B (B L L) (B L L)),S 4 (B (B L (B L L)) L),S 4 (B (B (B L L) L) L)]

计数验证：1个1叶树、1个2叶树、2个3叶树、5个4叶树，加起来正好9个元素，符合卡特兰数的计数规律（n个叶子的满二叉树数量正好是第n-1个卡特兰数）。

内容的提问来源于stack exchange，提问作者Melango41