On Friday, 21 November 2014 at 02:56:09 UTC, Andrei Alexandrescu
wrote:
As I like to say, this troika has inflicted a lot of damage on
both FP and those beginning to learn it:
* Linear-space factorial
* Doubly exponential Fibonacci
* (Non)Quicksort
These losers appear with depressing frequency in FP
introductory texts.
Be careful with that attitude. It is an excellent strategy to
start with the simple implementation and then move on to other
techniques in later chapters or more advanced texts.
https://www.haskell.org/haskellwiki/The_Fibonacci_sequence
https://www.haskell.org/haskellwiki/Memoization
Some compilers are even capable of adding memoization/caching
behind the scenes which brings naive fibonacci down to O(n) with
no change in the source.
Also, keep in mind that non-mutating quick sort has the same
space/time complexity as the mutating variant. The non-mutating
variant is no doubt faster on massively parallel hardware. You
can do quicksort on GPUs.
The landscape of performance and complexity is not so simple
these days.
