I have realised that the following program
fibMap :: [Integer] -> [Integer]
fibMap xs = 1 : 1 : (zipWith (+) xs $ tail xs)
fix :: (b -> b) -> b
fix f = f $ fix f
> take 100 $ fix fibMap
is surprisingly fast. It is much faster the than the recursive definition:
fib 0 = 1
fib 1 = 1
fib k = fib (k-1) + fib (k-2)
> fib 100
I am having trouble to understand to which procedural algorithm the fixpoint definition actually boils down to. Is it only fast because Haskell's compiler does some clever optimization, or is it intrinsically fast?
Let us unwrap the fixpoint a bit:
x = fix fibMap = fibMap $ fix fibMap
= 1:1:(zipWith (+) y $ tail y)
where y = fix fibMap = fibMap $ fix fibMap
Does the Haskell compiler recognize that x = y and "short-fuse"? Will it just learn more an more about the list x, or does it recompute everything from scratch for y?
I feel short-fusing would result in a fast algorithm whereas recomputing y would give something roughly equivalent to the recursive algorithm?
Are there any tricks/ways of thinking to make it easier to determine complexities for algorithms which use fixpoints? Is it sensitive to the evaluation tactics of the compiler?
The key idea is to share work. In the naive version, fib (n-2) is computed twice from scratch (fib n = fib (n-1) + fib (n-2) = fib (n-2) + fib (n-2) + fib (n-3)). In the list version, the argument xs represents the recursive call, which is evaluated once, and used twice.
fix fibMap = fibMap (fix fibMap)
= let xs = fix fibMap in
1 : 1 : zipWith (+) xs (tail xs)
One way to think about how this work is to change the goal from "how to compute the n-th Fibonacci number" to "how to compute the list of the first n Fibonacci numbers". For n > 2:
The first two Fibonacci numbers are 1 and 1;
The (n-2) remaining can be computed from the first (n-1) Fibonacci numbers, by zipping that list with itself.
It is still a recursive algorithm, but there is only one recursive call, which is how you avoid the exponential blow-up.
In fact from the above definition you can demonstrate formally, by equational reasoning, the following identity for take n (fix fibMap) (for n > 2):
take n (fix fibMap)
= let ys = take (n-1) (fix fibMap) in
1 : 1 : zipWith (+) ys (tail ys)
The above algorithm makes about n recursive calls, and for each call it zips a list of length at most n, so the complexity is at most quadratic (O(n^2)), and this is in fact a tight bound.
You might have expected a linear complexity bound (O(n)), but for that you have to tweak the algorithm a little. The problem of course is that the "zipping" operation at every step does a lot of redundant work.
This is the difference between these two definitions of fix:
fix f = f (fix f)
and
fix f = let self = f self in self
They are equivalent in the sense that they produce the same value, but they differ operationally: the second one executes much more efficiently in some cases (such as this one).
In the first definition, when f needs its argument, it will evaluate fix f again from scratch.
In the second definition, the argument of f is its own result, so when f needs its argument, it will use what it has already partially computed.
Now in the concrete case of defining the Fibonacci sequence, the definition using the first version of fix above is inefficient, because it makes infinitely many calls to fibMap (and thus zipWith):
fix fibMap = fibMap (fix fibMap) = fibMap (fibMap (fix fibMap)) = ...
whereas the second version uses fibMap only once:
fiblist = let self = fibMap self in self
-- equivalent definition
fiblist = fibMap fiblist