The conventional wisdom on data structures in functional languages is that immutability costs you. It was a big advance when Okasaki came up with algorithms that have an amortized complexity for lazy functional languages the same as the non-amortized complexity for the data structures with destructive update.
Work is going on in that area; check out Edward Kmett's post "Part I: Deamortized ST" about how to come up with a way to make the amortization unnecessary. (It's a bit reminiscent of Asimov's essay "Behind the Teacher's Back".) I'm hoping that will ultimately mean Haskell will be usable in still more situations.
(Actually, I should just say "read Edward Kmett's blog" period. It's all very good stuff.)
random notes and thoughts, mostly about Haskell these days, of a rather past middle-aged programmer
Monday, November 04, 2013
Subscribe to:
Post Comments (Atom)
Riddler Classic, May 23, 2020—Holy Mackerel!
Another one using Peter Norvig's word list . It turns out that the word "mackerel" has a curious property: there is exactly ...
-
"Why I'm Interested in Haskell" --not the writing of a fanboy, but of someone who I think fairly assessed the state of the pro...
-
So, how about that tree? It's tempting to do something like van Laarhoven describes, though I'd be tempted to put maxima on the left...
-
Another one using Peter Norvig's word list . It turns out that the word "mackerel" has a curious property: there is exactly ...
No comments:
Post a Comment