gistfile1.txt

Here's an explanation from 30k ft. of the generator namespace. There are three monads
involved, one of which simply contains the other two (but is not a monad transformer). They're
not named explicitly like this in the module, but let's call them: RoseTree, Generator and Gen.
Gen is the monad that is a wrapper around Gen (RoseTree a), to use Haskell types. A RoseTree
is simply an n-ary. In Haskell, it'd be defined like:

data RoseTree a = RoseTree a [RoseTree a]

In Clojure I represent it as a two-element vector, the first element being the node's value,
and the second being a lazy-sequence of the children. Since we use a lazy-seq, we can
represent very large trees. The top of the tree represents a randomly generated value, say
the number 15, and the rest of the tree represents all of the ways to shrink this value. All
of the functions that are named, or reference the word 'rose' related to this type. `return`
on a RoseTree simply creates a tree with a root, and no children. `bind` (>>=) is a little
difficult to describe with prose, but 'combines' two trees together, so the tree returned
from the function is 'bolted' onto the shape of the original tree. Check out join-rose to
see how this works. fmap does what you'd expect for a tree, simply applies the function
too all of the nodes.

The Generator monad (which has not yet been paramatarized to contain RoseTrees) is simple.
It's just a name for a function that takes a 'size' (Int) and a random number generator, and returns
an `a`. The Gen monad simply makes this `a` always be `RoseTree a`. `fmap` will apply
a function to all generated values, and bind allows you to create a new generator that depends
on a randomly generated value of a previous generator.

You can also read some more detail on my idea for how this would look in Haskell in my recent
mailing list post to the Haskell QuickCheck group [1]. That will show some more concrete types, which
may make things clearer. And feel free to reply with whatever questions you may have.