1

Consider the following Haskell code for computing the nth Fibonacci number.

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

This code is slow. We can optimize it by refactoring to a helper function that computes "iteratively", by "storing" all the relevant data to compute the recurrence with in its arguments, along with a "counter" that tells us how long to compute for.

fastfib :: Int -> Int
fastfib n = helper 1 0 n
  where
    helper a _ 1 = a
    helper a b i = helper (a + b) a (i - 1)

It seems like this optimization could apply more broadly as well. Does it have a name, in the functional programming community or elsewhere?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Eli Rose
  • 6,788
  • 8
  • 35
  • 55
  • 12
    This is not a simple refactoring. It completely changes the algorithm. At best, it is a form of advanced memoization: using memoization we would remember all the previously computed results, while in this case we only remember the last two since that's what we need. You can also see "dynamic programming" for a similar technique in algorithms. – chi Nov 22 '19 at 17:49
  • @chi Yes, I agree this is not simple refactoring. – Eli Rose Nov 22 '19 at 19:04
  • Are you familiar with memoization? – Thomas M. DuBuisson Nov 22 '19 at 19:58

1 Answers1

0

Yes, it's called accumulating parameter technique. (Here's one of my answers, about it).

It's closely related to , tail-recursion-modulo-cons ("TRMC"), , hylomorphisms, folding, etc.

Monoids enable the re-parenthesization 

a+(b+(c+...)) == (a+b)+(c+...) == ((a+b)+c)+...

which enables the accumulation. TRMC (which came to be explicitly known in the context of Prolog) is the same, just with lists; 

[a]++([b]++([c]++...)) == ([a]++[b])++([c]++...) == (([a]++[b])++[c])++...

and corecursion builds lists in top-down manner just like TRMC does.

The answer linked above contains a link to the technical report from 1974 by Friedman and Wise, which essentially talks about accumulation in the context of the + monoid, as an example.

There's no monoids in the Fibonacci example, but there's an accumulation of "knowledge" so to speak, as we go along from one Fibonacci number to the next.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • 1
    It's a bit of a stretch to say that this is closely related to [tag:monoids], [tag:tailrecursion-modulo-cons], [tag:corecusion], or hylomorphisms. – Aadit M Shah Nov 23 '19 at 03:32
  • @AaditMShah I disagree. I've expanded my answer with the explanations. Thanks for commenting! – Will Ness Nov 23 '19 at 10:12