This is the missing piece from my mental toolbox. I wish I'd known about it years ago.
Co-recursion is a principled way to turn a top-down algorithm into a bottom-up one. For instance, in Haskell, it's easy to write the fibonacci series from its definition:
fibonacci 0 = 1
fibonacci 1 = 1
fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)
But this is ridiculously inefficient. Until now, the only "principled" way I knew of to transform this into something sensible was through memoization, but that's still very wasteful.
With co-recursion in my toolkit, I can transform this into a form that generates the whole series as a stream:
fibonacci_series = 0: 1: more fibonacci_series
where
more f1: rest@(f2: _) = f1 + f2: more(rest)
And thanks to Haskell's lazy, garbage collected semantics, taking the nth element of the series (remembering to drop data I don't need) turns out to be equivalent to:
fibonacci n = fib n 0 1
where
fib 0 a b = a
fib n a b = fib (n-1) b (a+b)
Which is what we wanted. :-)
Co-recursion is a principled way to turn a top-down algorithm into a bottom-up one. For instance, in Haskell, it's easy to write the fibonacci series from its definition:
But this is ridiculously inefficient. Until now, the only "principled" way I knew of to transform this into something sensible was through memoization, but that's still very wasteful.With co-recursion in my toolkit, I can transform this into a form that generates the whole series as a stream:
And thanks to Haskell's lazy, garbage collected semantics, taking the nth element of the series (remembering to drop data I don't need) turns out to be equivalent to: Which is what we wanted. :-)