2

给定以下数据类型定义：

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

4 回答 4

7

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

...这确实是前十个加泰罗尼亚数字，所以我们可能做对了！

于 2015-01-23T01:12:04.390 回答
4

列表理解

[ (x,y) | x<-[1..] , y<-[1..] ]

首先考虑x=1并构建所有(1,y)可能y的 s 的所有对。然后是x=2和所有的(2,y)对。等等。

然而，有无限多的(1,y)对，所以x=2只会在无限长的时间后才考虑——也就是说，根本不会。

您的代码也遇到了同样的问题。

要查看可能的解决方案，您可以参考这个相关问题，利用 Omega monad 在所有情况下实现公平调度。

于 2015-01-22T23:46:27.967 回答
1

一种方法是跟踪树的大小（即Node使用的构造函数的数量。）

假设你有一个这样的函数，它使用n 个Node 构造函数返回树：

treesOfSize :: Int -> [FormTree]

那么allTrees可以定义为：

allTrees = concatMap treesOfSize [0..]

的定义treesOfSize可以递归定义，我会让你弄清楚：

treesOfSize 0 = [Empty]
treesOfSize n = [ Node t1 t2 | ... ]
于 2015-01-22T23:49:37.133 回答
1

control-monad-omega库似乎可以使用您的原始代码来解决问题：

{-# LANGUAGE MonadComprehensions #-}

import Control.Monad.Omega

data Empty = Empty | Node Empty Empty deriving Show

allPossibleTrees :: [Empty]
allPossibleTrees = Empty : 
    runOmega [Node x y | x <- each allPossibleTrees, y <- each allPossibleTrees]

前 10 棵树对我来说看起来不错：

*Main> mapM_ print $ take 10 allPossibleTrees 
Empty
Node Empty Empty
Node Empty (Node Empty Empty)
Node (Node Empty Empty) Empty
Node Empty (Node Empty (Node Empty Empty))
Node (Node Empty Empty) (Node Empty Empty)
Node (Node Empty (Node Empty Empty)) Empty
Node Empty (Node (Node Empty Empty) Empty)
Node (Node Empty Empty) (Node Empty (Node Empty Empty))
Node (Node Empty (Node Empty Empty)) (Node Empty Empty)
于 2015-01-24T11:15:41.963 回答