Oh, that's cool.

I sat for a course in Haskell while at IMSc. It was great fun initially but after a while I found it a little too erm, mathematical for me - the course was targeted at senior Math PhD and Post-doc students. And I was already sitting for a few courses too many... Will hopefully get back to it. Someday. :)

Enjoy!

(Sorry about the no-help with the Data.Map)

(Reply) (Thread)

Found you from ephermata. I'm pretty sure pure shuffling has to be at least O(n log n), since the naïve version allocates a full binary tree over the set to be shuffled. Even if you deforest and don't allocate that, there are n log n choice points, n log n examinations of a random value.

You might enjoy Oleg Kiselyov's perfect shuffle in Haskell, available at http://okmij.org/ftp/Haskell/perfect-shuffle.txt

(Reply) (Thread)

thanks. that was interesting, although i think it's a straw-man critique of the sort-based algorithm. here's a similar algorithm (also O(n log n)) that's much simpler than using trees:

1. initialize each of n buckets to empty lists
2. for each x in xs: insert x into a random bucket
3. permute each bucket using the quadratic algorithm
4. concatenate the permuted buckets.

same concept as the sort-based algorithm, avoids the identical-keys problem. i think the binary tree implementation is needlessly complex.

(Reply) (Parent) (Thread)