Generating recursive data with StreamData

Questions / Help
1

I am currently playing around with StreamData and I have problems with generating recursive data structures. There is StreamData.tree to generate trees, but I cannot apply the example presented there to my problem, since there is no root node with has a value except for the branches.

I use a simple functional tree which is either a :leaf or an inner node with a value, left and right children:

@type tree(g) :: :leaf | {:node, g, tree(g), tree(g) }

In Proper (and thus propcheck) and in QuickCheck I can use the following approach:

 def tree(g), do:
     one_of([
       :leaf,
       lazy {:node, g, tree(g), tree(g)}
      ])

How do I generate such a tree with StreamData? Since there is no lazy construction, I cannot call my generator recursively (which result in an endless loop) . A brief look into the implementation of StrreamData.tree() shows the usage of some internal functions to handle the recursion. But how do this properly in the spirit of the API?

Thanks!

4 Likes
2

The solution is rather simple: Use the tree function properly or define a recursive generator as in propcheck:

Using the tree function from StreamData:

def tree(value_gen), do:
  StreamData.tree(:leaf, fn child_gen -> {:node, value_gen, child_gen, child_gen})

The more complex but also more flexible solution is the recursive definition. It does not use an explicit lazy construction but uses the size parameter to restrict the height of the tree. Otherwise it could become quite large using all of your precious memory.

def tree(value_gen), do: sized(fn size -> tree_gen(size, g) end)
defp tree_gen(0, _g), do: :leaf
defp tree_gen(size, g), do:
   frequency([
      {1, tree_gen(0, g)},
      {9, ({:node, g, 
        resize(tree_gen(g), div(size, 2)),
        resize(tree_gen(g), div(size, 2))})}
   ])

The main difference is that the frequency between leaves and inner node, and the level of resizing is either abstracted away in tree() or an essential part of your own recursive generator. It depends on the requirements which of both approaches to choose.

3 Likes