Haskell quickcheck to generate and test rose trees?

Question

I am trying out a simple rose tree code.

data RoseT a = Leaf a | Node a [RoseT a] deriving (Show)

instance Eq (RoseT a) where
 (==) (Leaf a) (Leaf b) = a == b
 (==) (Node a rs1) (Node b rs2) = and ((a==b): (zipWith (==) rs1 rs2))
 (==) _ _ = False 

Can I use quickcheck to test the implementation of Eq instance ? if yes, how? if no, what is best alternative?

I also have a function that does the following:

appendPath :: (RoseT a) -> (RoseT (a,[a]))
appendPath rst = appendPath' [] rst 

appendPath :: [a] -> (RoseT a) -> (RoseT (a,[a]))
appendPath' p (Leaf a) = Leaf (a,p)
appendPath' p (Node a rs) = Node (a,p) (map (appendPath' (a:p)) rs)

The function appendPath takes a rose-tree as input and returns a rose-tree with the path from node to root in every node of the tree. This information I use in another function.

How do I use quickcheck to check this implementation on large sized rose-trees?

EDIT: As suggested by mhwombat, it seems impossible to write generator that takes type parameter as an argument. So here is my type parameter. I want to construct a RoseT of strings representing valid random arithmetic expressions, where, the arithmetic expressions themselves follow the following structure:

data Expr = Var String | AddExpr [Expr] | MulExpr [Expr] deriving Show

So, is there a way to generate random RoseT Expr where the Expr themselves are randomly generated using quickcheck only?

Thanks again mhwombat, for bearing with my baby-steps.

Answer 1

Unless I'm missing something, your Eq implementation of RoseT is the same as the default derived implementation. So you can just say

data RoseT a = Leaf a | Node a [RoseT a] deriving (Show, Eq)

and forget the instance Eq (RoseT a) where stuff.

The next question is whether or not this will meet your needs for testing. If you're testing with a floating-point type parameter, e.g., RoseT Double, then you need to allow for differences due to rounding. In that case what you need is a function that compares two trees and sees if the values are "close enough".

However, I suspect your RoseT implementation won't depend in any way on the type parameter. In that case, you could just test it with a nice simple type like Char or Int, and use == for any comparisons you need.

You have two type signatures for appendPath. I think the second one was supposed to be appendPath':

appendPath' :: [a] -> (RoseT a) -> (RoseT (a,[a]))

Now for how to test it. It would be best if you/QuickCheck have some control over the complexity of the trees being tested. This will help you because the simplest trees will be tested first, so you find bugs "early" (i.e., with simpler test cases that are easier to debug). You can do this by implementing a "sized" generator for your class. Here's one way to do it. The higher the value of the "size" parameter, the more levels the tree is likely to have.

type TestRoseT = RoseT Char

sizedArbTestRoseT :: Int -> Gen TestRoseT
sizedArbTestRoseT 0 = do
  c <- arbitrary
  return $ Leaf c
sizedArbTestRoseT n = do
  c <- arbitrary
  subtreeCount <- choose (0,n-1)
  subtrees <- vectorOf subtreeCount (sizedArbTestRoseT (n-1))
  return $ Node c subtrees

instance Arbitrary TestRoseT where
  arbitrary = sized sizedArbTestRoseT

prop_appendPath_does_something :: TestRoseT -> Property
prop_appendPath_does_something t = undefined -- stub

We can sample the test data that's generated like so:

λ> sample (sizedArbTestRoseT 2)
Node '\a' [Node '\RS' []]
Node '?' []
Node '\158' []
Node 'o' [Node 'E' []]
Node '\196' []
Node '4' [Node 'G' []]
Node ';' [Node 'f' []]
Node 'A' [Node '\CAN' []]
Node '!' []
Node 'q' [Node '\t' []]
Node '\'' [Node '\212' []]

Edit:

For your Expr type, we can write a generator like so:

sizedArbExpr :: Int -> Gen Expr
sizedArbExpr 0 = do
  s <- arbitrary
  return $ Var s
sizedArbExpr n = do
  es <- vectorOf 2 (sizedArbExpr (n-1))
  elements [AddExpr es, MulExpr es]

instance Arbitrary Expr where
  arbitrary = sized sizedArbExpr

We'll need to modify TestRoseT and its generator so that the complexity of the tree is consistent with the "size" parameter:

type TestRoseT = RoseT Expr

sizedArbTestRoseT :: Int -> Gen TestRoseT
sizedArbTestRoseT 0 = do
  c <- sizedArbExpr 0 -- changed this to keep complexity in bounds
  return $ Leaf c
sizedArbTestRoseT n = do
  c <- sizedArbExpr (n-1) -- changed this to keep complexity in bounds
  subtreeCount <- choose (0,n-1)
  subtrees <- vectorOf subtreeCount (sizedArbTestRoseT (n-1))
  return $ Node c subtrees

Testing these modifications gives something like:

λ> sample (sizedArbTestRoseT 3)
Node (MulExpr [MulExpr [Var "",Var ""],AddExpr [Var "",Var ""]]) [Node (MulExpr [Var "",Var ""]) [Node (Var "") []]]
Node (MulExpr [AddExpr [Var "",Var ""],AddExpr [Var "",Var ""]]) [Node (AddExpr [Var "",Var ""]) []]
Node (MulExpr [AddExpr [Var "\164D",Var "\151\246\FS"],MulExpr [Var ":\149j\EM",Var "h\253\255"]]) [Node (MulExpr [Var "\CAN\a\ACK",Var "\184"]) [Node (Var "t\154]\\") []],Node (MulExpr [Var "\135",Var "\f\DEL\\"]) [Node (Var "\SOH\DEL") []]]
Node (AddExpr [AddExpr [Var "",Var ""],MulExpr [Var "Kj\STXV",Var "D\141<s\187"]]) []
Node (AddExpr [MulExpr [Var "\252",Var "`"],MulExpr [Var "\167`t\196",Var ":\135\NULdr\237\167"]]) []
Node (AddExpr [MulExpr [Var "]\173\&28D\SOCom",Var "^\196\ETB2\216\&2\GS\ENQ\ENQ"],AddExpr [Var "$bB\212\SOH\146\234",Var "\DC3\213\&3\SUB\\}^\246(\200"]]) [Node (MulExpr [Var "l;\133\EM\147#\SUBN\\\t",Var "\235\151U\129m3|"]) [Node (Var "\NULb\133") []],Node (AddExpr [Var "\187\EOT\165S\207\r\"\RS",Var "4"]) []]
Node (MulExpr [MulExpr [Var "%0eK",Var "`N**k\FS6\NAK"],MulExpr [Var "'lUL\NAKRPc\ENQR",Var "j\232+`\FS@n"]]) [Node (AddExpr [Var "H\DC1C%\DC48<\t\ETX.L",Var "\235+\v\STXX,\NAK\SUBQc="]) [Node (Var "f\254oX?w\224\195~/") []]]
Node (AddExpr [AddExpr [Var "P",Var "\148G\STX\DEL*\136(\161\159\&7"],AddExpr [Var "\218\136-",Var "9?\128\159\b\b%3t}\131qe"]]) [Node (MulExpr [Var "\198\249\&4\176\193/}\DC28",Var ")Gl0ym\GS"]) [Node (Var ")\204\226qA\175") []]]
Node (MulExpr [MulExpr [Var "\t\186r.",Var "j\ENQ\183\NUL\NAK\129:rg[\170o\157g\238"],AddExpr [Var "\218F\226\248\156\225\&1",Var "vu\SOH\138+CKW\EM\167\&1n"]]) [Node (MulExpr [Var ",\241\158={o\182\"5\t\STX\ETX\DC2\218\162",Var "\197\&1"]) [Node (Var "u?a};\238") []]]
Node (MulExpr [MulExpr [Var "*",Var "R"],AddExpr [Var "\CAN8C",Var "\232V.\172ILy\162a"]]) []
Node (MulExpr [MulExpr [Var "\SI\240NF\249-\v$",Var "K`\STX\231w{"],MulExpr [Var "\DC1\255\209",Var "/\227\146\236\STX\185T3r\f"]]) [Node (MulExpr [Var "\229,\DLE\NAKwf[7P\160\DEL",Var "\134#\RS\SI0KCg\195\NAK\"\191\&6\243\193\SI"]) [Node (Var "\226\&7b8\f\EOTgF\171\GS}\189c\SUBc\ETX") []]]

By the way, you said "it seems impossible to write generator that takes type parameter as an argument". Actually it is possible to do that, however I don't think that's what you really want here.

Incidentally, it seems a bit unusual that you want to create a tree (RoseT) where the leaves contain binary trees (Expr). In other words, you're creating trees of trees. Of course, I don't know your application.