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

## Arvind Narayanan's journal

Research Blog | Web page

Arvind Narayanan
 [ Tags | algorithms, functional programming, haskell, permutation ]

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.

 From: 2009-09-16 06:34 pm (UTC) (Link)
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)
 From: 2009-09-19 09:18 pm (UTC) (Link)
Found you from . 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