arbtree.hs

import Test.QuickCheck
import Control.Monad

-- simple binary tree, with data stored at leaves
data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show,Eq)

-- only instances of Arbitrary typeclass can be
-- generated by QuickCheck random input generator
instance Arbitrary a => Arbitrary (Tree a) where
  arbitrary = sized arbTree

-- helper function to grow trees: see
-- https://www.cis.upenn.edu/~bcpierce/courses/advprog/lectures/lec18.pdf
-- for original source
arbTree 0 = liftM Leaf arbitrary
arbTree n = frequency
   [(1, liftM Leaf arbitrary),
    (4, liftM2 Node (arbTree (n `div` 2))
      (arbTree (n `div` 2)))]