[Haskell-cafe] QuickCheck and Pairing Heaps

[Matias Eyzaguirre]

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)?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100810/31475f85/attachment.html