>> What I wondered was, if one could hid the random plumbing in some data
>> structure, like the state monad, but less linear.
>
> This problem cries for a State monad solution - but you don't need to
> do it yourself, there's already a Random monad defined for you.

Yes, but I only need the random values inside splitOnMedia.  The rest
is just non-linear plumbing.  We do not know beforehand how many
random values a branch quicksort will consume --- neither do we ware
about the state of the random generator at the end.  Do you consider
the RandomMonad the best fit?