How does an instance of "Arbitrary" looks for a tree?

In our CS-Lectures we currently learn about QuickCheck in Haskell. Now I got a task to use QuickCheck with the following tree-type:

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

I have already written some necessery equations to check different properties of trees. I know, that I need an instance of "Arbitrary" to run the whole thing. So tried this:

instance Arbitrary Tree where
   arbitrary = sized tree'
     where tree' 0 = do a <- arbitrary
                        oneof [return (Leaf a)]
           tree' n = do a <- arbitrary
                        oneof [return (Leaf a), return (Node (tree' (n-1)) (tree' (n-1)))]

But now I am getting some errors such as:

Couldn't match type `Gen Tree' with `Tree'
      Expected type: a -> Tree
        Actual type: a -> Gen Tree
    * In an equation for `arbitrary':
          arbitrary
            = sized tree'
            where
                tree' 0
                  = do a <- arbitrary
                       ....
                tree' n
                  = do a <- arbitrary
                       ....
      In the instance declaration for `Arbitrary Tree'
   |
61 |      where tree' 0 = do a <- arbitrary
   |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

or:

    * Couldn't match type `Tree' with `Gen Tree'
      Expected type: Int -> Gen Tree
        Actual type: Int -> Tree
    * In the first argument of `sized', namely tree'
      In the expression: sized tree'
      In an equation for `arbitrary':
          arbitrary
            = sized tree'
            where
                tree' 0
                  = do a <- arbitrary
                       ....
                tree' n
                  = do a <- arbitrary
                       ....
   |
60 |    arbitrary = sized tree'
   |                      ^^^^^

I think the problem is that I am doing some kind of recursion when choosing a Node. Because in that case the subtrees of that node are not trees but more like "return trees". Hopefully you know, what I mean.

Can somebody help me with this?

Thank you :)

Solution

The simplest way to implement this is with:

instance Arbitrary Tree where
   arbitrary = frequency [
       (3, Leaf <$> arbitrary)
     , (1, Node <$> arbitrary <*> arbitrary)
     ]

Here the arbitrary functions in bold are the ones implement for the Tree instance. The arbitrary for Leaf is the arbitrary instance for an Int.

Here we thus specify that an arbitrary tree is a leaf with an arbitrary Int, or it is a Node with an arbitrary left and right sub-Tree.

or with sized :: (Int -> Gen a) -> Gen a:

instance Arbitrary Tree where
   arbitrary = sized go
        where go 0 = Leaf <$> arbitrary
              go n = oneof [Leaf <$> arbitrary, Node <$> go' <*> go']
                  where go' = go (n-1)

here the size specifies the depth of the tree, not the number of elements.