Problem
Write function which returns an arbitrary shuffle of a pair of lists.
shuffle :: PickingMonad m => ([a],[a]) -> m [a]
shuffle = undefined
More precise requirements:
1. shuffle (ys,zs) should run without error for any pair of lists ys, zs :: [a] (including the empty lists)
2. in the case of the monad m = IO, shuffle (ys,zs) should return a list that is a possible interleaving of ys with zs, in time proportional to the sum of the lengths of ys and zs
3. in the case of the monad m = Dist, shuffle (ys,zs) :: Dist [a] should give the uniform distribution on all possible interleavings of ys with zs.
Note the last requirement is a bit subtle. One way to get a uniform distribution is via the Gilbert-Shannon-Reeds model of shuffling, where the probability of picking the head of the shuffle from ys (respectively, from zs) is m/(m+n)(respectively, n/(m+n)), where m = length ys and n = length zs.