||[Sep. 16th, 2009|03:07 am]
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.