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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
