генерировать все двоичные деревья с размером n

Question

Я хотел бы написать функцию, которая возвращает все возможные двоичные деревья для любого заданного размера.

К сожалению, я понятия не имею, почему мое решение всегда возвращает пустой список, за исключением размера 1.

allTreesN :: Int -> t -> [Tree t]
allTreesN n t 
    | n == 0 = [ Leaf ]
    | otherwise = [(Node x t y) | i <- [0..n-1], x <- (allTreesN i t),y <- (allTreesN i t), size (Node x t y) == n]

Answer 1

Вы в основном генерируете все деревья размером i для x и y, а затем стремитесь построить дерево размером n.Это будет работать только если i = 2 *n.Но теперь возникает вторая проблема: мы никогда не сможем сгенерировать здесь дерево размером 1, поскольку 1 не может быть разделено на два.Поскольку мы не можем сгенерировать дерево размером 1, мы не можем сгенерировать деревья с размером 2 и т. Д.

Таким образом, мы должны убедиться, что мы генерируем деревья правильного размера.Мы можем сделать это, сгенерировав дерево размером i, а другое - размером n-i-1.Если мы создаем узел такого размера, мы точно знаем, что размер узла, несущего эти поддеревья, имеет размер n, поэтому мы можем даже опустить проверку.

Итак, правильная реализация:

allTreesN :: Int -> a -> [Tree a]
allTreesN 0 _ = [Leaf]
allTreesN n v = [Node l v r | i <- [0..n-1],
                              l <- allTreesN i v,
                              r <- allTreesN <b>(n-1-i)</b> v]

Например:

Prelude> allTreesN 0 'a'
[Leaf]
Prelude> allTreesN 1 'a'
[Node Leaf 'a' Leaf]
Prelude> allTreesN 2 'a'
[Node Leaf 'a' (Node Leaf 'a' Leaf),Node (Node Leaf 'a' Leaf) 'a' Leaf]
Prelude> allTreesN 3 'a'
[Node Leaf 'a' (Node Leaf 'a' (Node Leaf 'a' Leaf)),Node Leaf 'a' (Node (Node Leaf 'a' Leaf) 'a' Leaf),Node (Node Leaf 'a' Leaf) 'a' (Node Leaf 'a' Leaf),Node (Node Leaf 'a' (Node Leaf 'a' Leaf)) 'a' Leaf,Node (Node (Node Leaf 'a' Leaf) 'a' Leaf) 'a' Leaf]