Fibonacci

As of March 2020, School of Haskell has been switched to read-only mode.

It is more or less a joke that all that functional programmers care about are ways to compute the Fibonacci numbers.

fibs = 1:1:zipWith (+) fibs (tail fibs)

Our primary benchmark suite for Haskell is named nofib after all.

But what if we embrace this predilection? What tools and powers do we gain?

Part 1: Leonardo Random Access Lists 28 Apr 2015Edward Kmett

Here I derive a data structure based on Leonardo numbers that can be used as a random-access list with an eye towards branch-prediction benefits.
Part 2: Open-Ended Fibonacci Search 13 Oct 2015Edward Kmett

Here we derive an open-ended form of Fibonacci search and explore the structure of homogeneous linear recurrences.