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/Combinatori...

If I may, I'd like to reference the paper by Jerzy Kaczmarczuk: "Generating power of lazy semantics": https://karczmarczuk.users.greyc.fr/arpap/lazysem.pdf It defines much more than Fibonacci numbers using similar techniques and beyond. Techniques there allow expression of multibody dynamics from Lagrangian. This gives a solution to such problems with time power series. This is not a closed form solution, yet very useful one. вс, 19 янв. 2025 г. в 15:45, 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 _______________________________________________ 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.