import Control.Monad

data Tree a
    = Nil
    | Branch a (Tree a) (Tree a)
    deriving (Show, Eq)

notEach :: Tree Bool -> [Tree Bool]
notEach = go where
    go :: Tree Bool -> [Tree Bool]
    go Nil = mempty
    go (Branch x l r)
        =  [Branch (not x) l r]
        <> fmap (\lU -> Branch x lU r) (go l)
        <> fmap (\rU -> Branch x l rU) (go r)

procreateL :: Int -> Tree Bool
procreateL 0 = Nil
procreateL n = Branch (n `rem` 2 == 0) (procreateL (n - 1)) (procreateL (n `div` 2))

procreateR :: Int -> Tree Bool
procreateR 0 = Nil
procreateR n = Branch (n `rem` 2 == 0) (procreateR (n `div` 2)) (procreateR (n - 1))

test :: IO ()
test = do
    guard $ notEach (procreateL 3) == [Branch True (Branch True (Branch False Nil Nil) (Branch False Nil Nil)) (Branch False Nil Nil),Branch False (Branch False (Branch False Nil Nil) (Branch False Nil Nil)) (Branch False Nil Nil),Branch False (Branch True (Branch True Nil Nil) (Branch False Nil Nil)) (Branch False Nil Nil),Branch False (Branch True (Branch False Nil Nil) (Branch True Nil Nil)) (Branch False Nil Nil),Branch False (Branch True (Branch False Nil Nil) (Branch False Nil Nil)) (Branch True Nil Nil)]
    guard $ notEach (procreateR 3) == [Branch True (Branch False Nil Nil) (Branch True (Branch False Nil Nil) (Branch False Nil Nil)),Branch False (Branch True Nil Nil) (Branch True (Branch False Nil Nil) (Branch False Nil Nil)),Branch False (Branch False Nil Nil) (Branch False (Branch False Nil Nil) (Branch False Nil Nil)),Branch False (Branch False Nil Nil) (Branch True (Branch True Nil Nil) (Branch False Nil Nil)),Branch False (Branch False Nil Nil) (Branch True (Branch False Nil Nil) (Branch True Nil Nil))]
    guard $ length (notEach $ procreateL 150) == 1564307
    guard $ length (notEach $ procreateR 150) == 1564307
    
main = test