Course-of-value recursion via laziness/infinite tables as return values

Show and Tell
1

I have never seen in articulated that laziness handles course-of-value recursion efficiently, though the technique has been used for years.

Turns out to be common in combinatorics, Reinhard Zumkeller has a bunch of examples (in Haskell!) on OEIS.

I wrote a note on it as filling in for memoization in other languages: http://vmchale.com/static/serve/Comb.pdf

3 Likes
2

Thanks Vanessa. emm maybe it’s just me, but your first sentence seems to have a typo, and I can’t figure out how/where to correct it.

  • never seen i[t] articulated that ??
  • laziness allows ??
  • laziness handles ??
  • the “efficiently” seems to be rather floating about at the end of the phrase. What is it that’s rendered efficient? And do you mean time-efficient or space-efficient or both or maybe rather achieves succinct/elegant code, not wrt run-time metrics?

course-of-values recursion as a term of art. “is a technique for …”

More on c-of-v at planetmath, Stanford Encyclopedia.

1 Like
3

Ah thanks! I edited the post.

If one naîvely writes

fibs :: Integer -> Integer
fibs 0 = 1
fibs 1 = 1
fibs n = fibs (n-1) + fibs (n-2)

Then computing (say) F_5 will proceed as:

\begin{align*}F_5&=F_4+F_3 \\ &=(F_3+F_2) + (F_2 + F_1) \\ &= ((F_2 + F_1) + ((F_1 + F_1) + F_1) \\ & \vdots \end{align*}

which expands the whole tree for F_3 twice!

The example

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

gets those values from fibs, which is shared between fibs and tail fibs!

4

Your definition of catalan is cut off when I view it in the pdf

catalan :: [Integer ]
catalan = 1 : 1 : [sum [(−1) ↑ (k + 1) ∗ (pc (n − ((k ∗ (3 ∗ k − 1)) /. 2)) + pc (n − ((k ∗ (3 ∗ k + 1)) /. 2))) |
  where
    pc m | m ⩾ 0 = part !! m | otherwise = 0
    infixl 6 /.
    (/.) = quot

Also I think you meant to use catalan where you wrote part