fork(1) download
copy 
  1. import Control.Monad
  2.  
  3. data Tree a
  4.     = Nil
  5.     | Branch a (Tree a) (Tree a)
  6.     deriving (Show, Eq)
  7.  
  8. notEach :: Tree Bool -> [Tree Bool]
  9. notEach = \t -> go t id [] where
  10.     go :: Tree Bool -> (Tree Bool -> Tree Bool) -> [Tree Bool] -> [Tree Bool]
  11.     go Nil wrap acc = acc
  12.     go (Branch x l r) wrap acc
  13.         = wrap (Branch (not x) l r) :
  14.           go l (\lU -> wrap (Branch x lU r))
  15.           (go r (\rU -> wrap (Branch x l rU)) acc)
  16.  
  17. procreateL :: Int -> Tree Bool
  18. procreateL 0 = Nil
  19. procreateL n = Branch (n `rem` 2 == 0) (procreateL (n - 1)) (procreateL (n `div` 2))
  20.  
  21. procreateR :: Int -> Tree Bool
  22. procreateR 0 = Nil
  23. procreateR n = Branch (n `rem` 2 == 0) (procreateR (n `div` 2)) (procreateR (n - 1))
  24.  
  25. test :: IO ()
  26. test = do
  27.     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)]
  28.     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))]
  29.     guard $ length (notEach $ procreateL 150) == 1564307
  30.     guard $ length (notEach $ procreateR 150) == 1564307
  31.  
  32. main = test
Success #stdin #stdout 0.63s 134544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7gU4IZ
language:
Haskell (ghc 8.4.4)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!