Hi Manlio, Manlio Perillo wrote:
For my Netflix Prize project I have implemented two reusable modules. The first module implements a random shuffle on immutable lists... The second module implements a function used to partition a list into n sublists of random length.
Very nice!
If someone is interested (and if Oleg give me permission), I can release them as a package on Hackage.
Please do that. While I think Oleg's tree method is beautiful, in practice it may be re-inventing the wheel. I haven't tested it, but I doubt that this implementation is much better than using the classical shuffle algorithm on an IntMap. It's essentially the same tree inside. That's what I usually use for this, and it works fine.
In future I can add an implementation of the random shuffle algorithm on mutable arrays in the ST monad.
I've tried that in the past. Surprisingly, it wasn't faster than using trees. Perhaps I did something wrong. Or perhaps the difference only becomes apparent for huge lists. As you point out, your partition algorithm is not fair. Using your Random.Shuffle and a well-know trick from combinatorics, you can easily get a fair partitions function: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2485#a2495 Regards, Yitz