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

Question

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 :)

Answer 1

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.

Answer 2

This can be derived using the generic-random library

{-# Language DataKinds     #-}
{-# Language DeriveGeneric #-}
{-# Language DerivingVia   #-}

import GHC.Generics
import Generic.Random.DerivingVia
import Test.QuickCheck

-- ghci> :set -XTypeApplications
-- ghci> sample @Tree arbitrary
-- Node (Leaf 0) (Node (Leaf 0) (Node (Leaf 0) (Node (Node (Leaf 0) (Leaf 0)) (Leaf 0))))
-- Leaf 0
-- Leaf (-2)
-- Leaf 5
-- Leaf 0
-- Leaf 2
-- Leaf 1
-- Leaf 7
-- Node (Leaf (-7)) (Leaf (-2))
-- Node (Leaf 4) (Node (Leaf 0) (Leaf 3))
-- Node (Leaf 5) (Leaf (-2))
data Tree = Leaf Int | Node Tree Tree
  deriving
  stock (Eq, Show, Generic)

  deriving Arbitrary
  via GenericArbitraryRec '[2, 1] Tree

Let me know if there is something wrong with the distribution!