import Data.List
import Test.QuickCheck

-- Tree data structure, functions

data Tree = Nil | Node Tree Int Tree deriving (Show, Eq)

tInsert :: Int -> Tree -> Tree
tInsert x Nil = Node Nil x Nil
tInsert x (Node lt y rt)
    | x > y     = Node (tInsert x lt) y rt
    | otherwise = Node lt y (tInsert x rt)

tInsertMany :: [Int] -> Tree -> Tree
tInsertMany [] t = t
tInsertMany (x:xs) t = tInsertMany xs (tInsert x t)

tFromList :: [Int] -> Tree
tFromList xs = tInsertMany xs Nil

-- Functions specific to the problem

nexts :: [Tree] -> [(Int, [Tree])]
nexts [] = []
nexts (t:ts) =
    case t of
        Nil -> nexts ts
        Node c1 i c2 -> (i, ts ++ filter (/=Nil) [c1, c2])
                      : map (\(t_, ts_) -> (t_, t : ts_)) (nexts ts)

alls :: [Tree] -> [[Int]]
alls [] = [[]]          -- These two lines are to properly handle
alls (Nil:ts) = alls ts -- Empty lists, and lists of Nil trees -> no trees.
alls ts = concat $ map (\(i, ts_) -> map (i:) $ alls ts_) $ nexts ts

-- Stuff related to tests

prop_sameTree :: Tree -> Property
prop_sameTree t = forAll (elements (alls [t])) $ \is -> t == tFromList is

prop_noTwice t = let as = alls [t] in as == nub as

instance Arbitrary Tree where
    arbitrary = do
        k <- choose (0,10) :: Gen Int
        is <- sequence [ arbitrary | _ <- [1..k] ]
        return $ tFromList is

-- And here we go.

main :: IO ()
main = do
    quickCheckWith stdArgs { maxSuccess = 10000 } prop_sameTree
    quickCheckWith stdArgs { maxSuccess = 1000 } prop_noTwice