4 ms·
The implementation of Fibonacci numbers in Haskell doesn't use memoization at all. It's the dumbest possible implementation. Here's an optimized one: fibs
by kccqzy 4y ago
The implementation of Fibonacci numbers in Haskell doesn't use memoization at all. It's the dumbest possible implementation. Here's an optimized one:
fibs = 0 : scanl (+) 1 fibs
It also showcases Haskell's lazy list and recursive definition of data (not your usual recursive function).
- gmiller123456 4y agoI don't think any claims were made to the an optimal approach nor utilize optimal language features.
- xdavidliu 4y agothere's a reasonable expectation that a repo named "cool algorithms" won't use extremely dumb exponential-time versions when linear-time ones exist. Also in this case there's a logarithmic-time one that does repeated squaring of a 2x2 matrix.
- im3w1l 4y agoArithmetic on bignums is not O(1), but rather depends on the size of the numbers. This is important when considering say the repeated matrix squaring vs an evaluation of the closed form. They both beat naive exponential time algos, of course.
- ianai 4y ago
- green_on_black 4y ago? The implementation is the dumb thing though?
- deleted 4y ago[deleted]
- kazinator 4y agoThey have FastFibonacci as a separate category (with only a Python implementation, currently).
- tromp 4y agoRight; the page https://the-algorithms.com/algorithm/fibonacci-numbers https://the-algorithms.com/algorithm/fibonacci-numbers details a smart algorithm using matrix powers and then lists implementations for many languages. But the Haskell implementation is the dumb exponential one rather than the smart one shown. Btw, another less cryptic way to generate the list of Fibonacci numbers is fibs = f 0 1 where f a b = a : f b (a+b)
- bitlax 4y agoIsn't this an open source library? Why are you gripping here instead of making a PR?