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.
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.
If this is the kind of thing that keeps you up at night, you should just be using C.
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.