<font class="Apple-style-span" face="&#39;courier new&#39;, monospace">Hi, I&#39;m trying to figure out QuickCheck and how to generate arbitrary test data form complex data structures; I thought an interesting experiment would be Pairing Heaps.</font><div>
<font class="Apple-style-span" face="&#39;courier new&#39;, monospace">A pairing heap is essentially just a tree whose nodes obey the heap property (for all nodes A in a pairing whose nodes can be compared, the value of A is greater then the value of any descendants of A).</font></div>
<div><font class="Apple-style-span" face="&#39;courier new&#39;, monospace">I came with a definition that I think seems reasonable</font></div><div><font class="Apple-style-span" face="&#39;courier new&#39;, monospace">\begin{code}</font></div>
<div><font class="Apple-style-span" face="&#39;courier new&#39;, monospace">  data (Ord a) =&gt; Heap a = Heap a [Heap a]</font></div><div><font class="Apple-style-span" face="&#39;courier new&#39;, monospace">\end{code}</font></div>
<div><font class="Apple-style-span" face="&#39;courier new&#39;, monospace">But I cannot think of a way to generate arbitrary heaps, I see three main issues:</font></div><div><font class="Apple-style-span" face="&#39;courier new&#39;, monospace">1. Based on the examples I have seen, I understand how you could define arbitrary so that it uses frequency to choose either a leaf or a branch, but how would you generate a variable number of children?</font></div>
<div><font class="Apple-style-span" face="&#39;courier new&#39;, monospace">2. That would hardcode the probably size of the heap, how would you define an arbitrary heap that was dependent on some sort of size parameter?</font></div>
<div><font class="Apple-style-span" face="&#39;courier new&#39;, monospace">3. The way I see it, you could generate arbitrary heaps of type A (where A is an instance of Arbitrary and Ord), but how would you make sure that each node of the generated tree was heapy (the max of all its descendants)?</font></div>