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

[Henning Thielemann]

On Sun, 19 Jan 2025, Vanessa McHale wrote:

> 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)

This example is old and well-known, right?


> 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 have:

catalanNumbers :: Num a => [a]
catalanNumbers =
    let xs = 1 : PowerSeries.mul xs xs
    in  xs

https://hackage.haskell.org/package/combinatorial-0.1.1/docs/src/Combinatorics.html#catalanNumbers