Хотел подменить Data.HashTable на IORef (Data.Map.Map key value)...
...в процессе получил Stack overflow.
(это я вот с этим разбирался: http://flyingfrogblog.blogspot.com/2009/04/f-vs-ocaml-vs-haskell-hash-table.html)
Занявшись выяснением, почему же stack overflow, несмотря на тщательно расставленные 'seq' и bang patterns, наткнулся на вот это: Speaking as someone who's been doing OO for many years, and recently has been building a largeish project requiring a good deal of speed (a real-time automated options trading system) in Haskell...
Оба-на!
И позволю себе процитировать значительный кусок его ответа:Generally the problem is not that "you really do need a hash table," but that you need access to certain data within some given time constraints (which may well be, "as fast as possible on some given hardware."). For that, you look around and do what you need to do. If that includes introducing mutability, I don't see a big problem with that, and you can do it in Haskell, though it might not be as convenient as it is in other languages. But do keep in mind, if you have a problem of this nature, it's certainly not going to be as simple as, "use a generic hash table and you're done." Extremely high performance for particular functionality on a particular hardware platform invariably takes a lot of work, and usually more than a few tricks. Preferring one language implementation over another just because it has some particular thing that works better than it does in other languages is, in my opinion, a rather unsophisticated approach to software engineering that is not likely to consistently produce good results.
Сильнее я не мог бы возразить, перефразируя Ломоносова.
PS
Кстати, там было вот ещё что: We present theoretical algorithms for sorting and searching multidimensional data and practical C implementations for the application where keys are character strings. The sorting algorithm, an amalgam of Quicksort and radix sort, is competitive with the best known C sort codes. The searching algorithm, an amalgam of tries and binary search trees, is faster than hashing and other commonly used search methods. The basic ideas behind the algorithms date back at least to the 1960s, but their practical utility has been overlooked. Analytic results and extensions to more difficult string processing problems are also included.
(это я вот с этим разбирался: http://flyingfrogblog.blogspot.com/2009/04/f-vs-ocaml-vs-haskell-hash-table.html)
Занявшись выяснением, почему же stack overflow, несмотря на тщательно расставленные 'seq' и bang patterns, наткнулся на вот это: Speaking as someone who's been doing OO for many years, and recently has been building a largeish project requiring a good deal of speed (a real-time automated options trading system) in Haskell...
Оба-на!
И позволю себе процитировать значительный кусок его ответа:Generally the problem is not that "you really do need a hash table," but that you need access to certain data within some given time constraints (which may well be, "as fast as possible on some given hardware."). For that, you look around and do what you need to do. If that includes introducing mutability, I don't see a big problem with that, and you can do it in Haskell, though it might not be as convenient as it is in other languages. But do keep in mind, if you have a problem of this nature, it's certainly not going to be as simple as, "use a generic hash table and you're done." Extremely high performance for particular functionality on a particular hardware platform invariably takes a lot of work, and usually more than a few tricks. Preferring one language implementation over another just because it has some particular thing that works better than it does in other languages is, in my opinion, a rather unsophisticated approach to software engineering that is not likely to consistently produce good results.
Сильнее я не мог бы возразить, перефразируя Ломоносова.
PS
Кстати, там было вот ещё что: We present theoretical algorithms for sorting and searching multidimensional data and practical C implementations for the application where keys are character strings. The sorting algorithm, an amalgam of Quicksort and radix sort, is competitive with the best known C sort codes. The searching algorithm, an amalgam of tries and binary search trees, is faster than hashing and other commonly used search methods. The basic ideas behind the algorithms date back at least to the 1960s, but their practical utility has been overlooked. Analytic results and extensions to more difficult string processing problems are also included.