[Haskell-cafe] Course-of-value recursion by defining a sequence as a self-referential infinite list

[Vanessa McHale]

Laziness turns out to allow course-of-value recursion where one might use memoization in other languages. But I hadn’t seen this articulated!

Famously, one can use this to define the Fibonacci numbers, viz.

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

Or the Catalan numbers:

catalan :: [Integer]
catalan = 1 : 1 : [ sum [ (-1)^(k+1) * (pc (n - ((k*(3*k-1)) /. 2)) + pc (n - ((k*(3*k+1))/.2))) | k <- [1..n] ] | n <- [2..] ]
  where
    pc m | m >= 0 = part !! m | otherwise = 0

    infixl 6 /.
    (/.) = quot

I wrote up the example: http://vmchale.com/static/serve/Comb.pdf

Reinhard Zumkeller has a lot of examples on OEIS: https://oeis.org/A000081

Cheers,
Vanessa McHale
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20250119/da819eed/attachment.html>