Course-of-value recursion by defining a sequence as a self-referential infinite list

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

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.