Сформировать все возможные деревья

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

Вот хороший трюк, напоминающий стандартный трюк чисел Фибоначчи. Мы построим ленивый список; каждый член списка будет списком всех деревьев с заданным числом узлов. Есть только одно дерево без узлов, 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, так что мы, вероятно, получили это право!

Answer 2

Список понимание

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

начинается с рассмотрения x=1 и построения всех пар (1,y) для всех возможных y s. Затем следует x=2 и все пары . и так далее.

Однако существует бесконечное количество пар (1,y), поэтому x=2 будет рассмотрен только после бесконечного количества времени, то есть совсем нет.

Ваш код испытывает ту же проблему.

Чтобы увидеть возможное решение, вы можете обратиться к this related question, используя монуру Омега, чтобы добиться справедливого планирования среди всех случаев.

Answer 3

Один из способов следить за размером дерева

Предположит, вы имели такую ​​функцию, которая возвратила дерева, используя именно п Узел конструктора (то есть количество Node конструкторов используются.):

treesOfSize :: Int -> [FormTree] 

Тогда allTrees может быть определен как:

allTrees = concatMap treesOfSize [0..] 

Определение treesOfSize может быть рекурсивно, которые я дам вам понять:

treesOfSize 0 = [Empty] 
treesOfSize n = [ Node t1 t2 | ... ] 

Answer 4

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)