Hi, I'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.

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).

I came with a definition that I think seems reasonable

\begin{code}

data (Ord a) => Heap a = Heap a [Heap a]

\end{code}

But I cannot think of a way to generate arbitrary heaps, I see three main issues:

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?

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?

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)?