这是一个很好的技巧,让人想起标准的斐波那契数字技巧。我们将建立一个惰性列表;列表中的每个成员都是具有给定节点数的所有树的列表。只有一棵树,没有节点,Empty
,这将作为我们的基本案例。建造所有的树n
节点,我们假设我们已经知道如何构建树0
, 1
, 2
, ..., n-1
节点。然后我们将不确定地选择一组总和为n-1
并卡住了Node
on top.
In code:
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]
...这确实是前十名加泰罗尼亚语号码 http://oeis.org/A000108,所以我们可能是对的!