4 ms·
Following links in your 1), I liked https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf 'The Genuine Sieve o
by somewhereoutth 6y ago
Following links in your 1), I liked https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf 'The Genuine Sieve of Eratosthenes' by Melissa E. O’Neill. Somewhat damning and to your point.
Are there any theoretical barriers to writing algorithms in a pure and lazy language with the same space/time complexity as a side-effectful and strict language? I suppose quicksort (also mentioned) is an obvious candidate for study in this regard.
- spekcular 6y agoThere's also hash tables. IIRC, Haskell didn't have a good hash table implementation until relatively recently because people religiously avoided mutable data structures. (And the implementation I'm thinking of is not purely functional.)
- centimeter 6y agoHaskell has had good HAMTs for quite some time. There isn’t really any benefit to using a mutable hash table over that. In fact, it would probably be slower given the way copying GC works with mutable values.
- spekcular 6y agoYes, there is a benefit: correctly implemented hash tables are faster. Haskell's GC may prevent a good implementation, but that's a problem with Haskell, not with hash tables.
- yakshaving_jgt 6y agoWriting the fastest possible implementation of something is rarely a valid business goal. The ideal is the midpoint on a Venn diagram of 1) fast enough for our purposes, 2) logically robust, 3) cheap to implement. Besides, if something absolutely must be the fastest implementation possible and this can’t be done in Haskell, then there’s no reason why one couldn’t drop to the FFI at that point. You could even use template Haskell and write inline-C. It works.
- deleted 6y ago[deleted]
- centimeter 6y agoA marginally faster mutable hash table is not really useful for much. If that 30% speedup or whatever is going to make or break your application, a single hash table was the wrong choice anyway. If this is the kind of thing that keeps you up at night, you should just be using C.
- tome 6y agoFTI, HAMT = hash array mapped trie
- insulanus 6y agoThanks for linking this. I just read it, and that is some DAMN fine writing. Sometimes when I complain about jargon and bad writing in scientific papers, people argue back that the author has to be precise. This paper makes it clear that these are orthogonal issues. Writing is a skill, too. The author is being extremely technical and rigorous, but she is also CLEAR. Quite the badass.
- todd8 6y agoSacrebleu, how can this be? The Haskell one-liner compiles so it must be the genuine sieve of Eratosthenes.