Naive functional fibonacci is pretty sad performance-wise. Even if you are using a lazy, memoizing language it probably isn't as good as the imperative version that only has to keep track of the last 2 values as it moves on up towards the final n. How would we ever have a system that could look at something like fibonacci and transform it magically (which is of course in a lot of ways a really bad, dangerous, idea because it makes debugging even harder in the long run perhaps) into something sane from the perspective of loads and stores?