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

[Vanessa McHale]

Yes, the Fibonacci example and its connection to laziness is old! Not sure if it’s ever been named ‘course-of-value recursion’ or its corresponding strong induction. 

> On Jan 19, 2025, at 10:15 AM, Henning Thielemann <lemming at henning-thielemann.de> wrote:
> 
> 
> 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