import Test.QuickCheck
import Control.Monad

data Filesystem = Folder [Filesystem]
                | File
                deriving Show

instance Arbitrary Filesystem where
  arbitrary = sized arbitraryFS
    where arbitraryFS 0 = return File
          arbitraryFS n = frequency [ (1, return File)
                                    , (n, fmap Folder . vectorOf 5 . arbitraryFS $ n `div` 2) ]

numFiles1 :: Filesystem -> Int
numFiles1 File = 1
numFiles1 (Folder xs) = sum $ map numFiles1 xs

numFiles2 :: Filesystem -> Int
numFiles2 f = let (folders, files) = count f in files
  where count File = (0, 1)
        count (Folder f) = foldr (\(x,y) (xx,yy) -> (x+xx,y+yy)) (1,0) $ map count f

prop_fs1 :: Filesystem -> Bool
prop_fs1 fs = numFiles1 fs == numFiles2 fs