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.

Siegel

What would you like to test? It's certainly possible to use quickcheck to test properties about your tree but what did you have in mind? – Land

your RoseT definition seems incorrect. Rose-trees shouldn't have Leaf pattern in their ADT, as with that definition it is it is ambiguous whether leaf nodes should be written as Leaf 42, or Node 42 []. It is ambiguous because those two expressions should be equal, but they are not. – Hypsometer

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.

Spoor

Thanks. yes, my RoseT impl doesn't depend much on type parameter. But the subsequent use of RoseT does. Something like phantom types. For instance, I want to use it to process strings with certain properties, like, strings that are valid arithmetic expressions. I have edited the question to add this information. – Siegel

I am facing a similar issue. The type parameter (in Tree a) is not important, but the functions I want to test with QuickCheck have the type parameter in their signature, and I can't change these to refer to some TestRoseT type. Is it possible to change the generator so that trees of characters can be used to test my functions? – Unarmed

@RichAshworth In general, when you have a type with a type parameter (e.g., Tree a) you probably only need to test it with one type. E.g., once you've tested Tree Char, you know it will work for Tree Int. So similar to the example above, you can define type TestTree = Tree Char, write a generator for TestTrees, and write properties to test. The original functions will still have type signatures with Tree a. The only place TestTree will be used is in your test code. If this explanation isn't clear, you may want to open a new question, and link to this one. – Spoor

Thanks @Spoor I think that makes sense. Could you give an example implementation of the prop_appendPath_does_something function? The properties I had defined are just of the Property type... – Unarmed

@RichAshworth Suppose you have addNode and containsNode functions that operate on your trees. Then you might define prop_addNode_works n t = property $ (addNode t n) 'containsNode' n, which verifies that after you add a node, it's actually in the tree. – Spoor