Log in

No account? Create an account
Haskell - Arvind Narayanan's journal — LiveJournal [entries|archive|friends|userinfo]

Haskell [Sep. 16th, 2009|03:07 am]
Arvind Narayanan
[Tags|, , , ]

I started learning Haskell today. After a couple of hours of learning the syntax, I decided to dive in and write a function to shuffle a list, because linear-time permutation is non-trivial in pure functional languages. (The standard idiom translates to a quadratic algorithm because it is fundamentally destructive.)

I think I can get linear-time by assuming that the associative array operations in Data.Map are O(1), but in reality they have a logarithmic cost, since they are implemented as binary trees unlike Python's dictionaries which use hash tables. Besides, this was literally day 1 so I wasn't comfortable jumping into Data.Map.

So I ended up with something not particularly satisfactory, but I did learn some Haskell in the process. Any comments/criticism greatly appreciated.

Edit. Does anyone know if linear-time permutation is even possible in a functional setting? I thought I found a paper that did that but it turned out to be a simpler problem.

[User Picture]From: kadambarid
2009-09-16 06:34 pm (UTC)
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. :)


(Sorry about the no-help with the Data.Map)
(Reply) (Thread)
[User Picture]From: nakor
2009-09-19 09:18 pm (UTC)
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)
[User Picture]From: arvindn
2009-09-21 07:15 am (UTC)
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)