Vanessa McHale writes:

I came up with a one-liner for computing coefficients of the generating function for integer partitions:

part :: Int → [Integer ] part n = take n $ product [cycle (1 : replicate n 0) | n ← [0 . . (n − 2)]]

Karczmarczuk’s solution via the Haskell prelude:

part = 1 : b 1 where b n = (1 : b (n + 1)) + (replicate n 0 ++ b n)

This is broken code, no?, just 2 reasons I can spot why: - function 'b n' calls 'b n' unconditionally (infite loop) - What is the reutrn type of 'b'? It seems like it returns list, but the return value is in the form 'a + b' , where (+) is instance of num so I don't think prelude contains any ad-hoc definition of (+) that returns list

Looks like my attempt to paraphrase of Karczmarczuk’s solution skewered the performance. For efficiency it should be part = 1 : b 1 where b n = p where p = (1 : b (n + 1)) + (replicate n 0 ++ p) which is what is in Karczmarczuk’s paper (editing as necessary so replicate can be used as bxyn)

On Jan 22, 2025, at 7:01 AM, Vanessa McHale wrote:

I came up with a one-liner for computing coefficients of the generating function for integer partitions:

part :: Int → [Integer ] part n = take n $ product [cycle (1 : replicate n 0) | n ← [0 . . (n − 2)]]

Karczmarczuk’s solution via the Haskell prelude:

part = 1 : b 1 where b n = (1 : b (n + 1)) + (replicate n 0 ++ b n)

cycle and replicate are really underrated!

...

On Jan 20, 2025, at 8:54 AM, Douglas McIlroy wrote:

...

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

This example of a generating function come to life as a program deserves to be better known. Bill Burge presented it 50 years ago in "Recursive Programming Techniques", Addison-Wesley, 1975. I revisited it in "Power series, power serious", JFP 9 (1999) 323-335, where, with overloadied arithmetic, it became ts = 1 : ts^2 The technique is laid bare in ten one-liners at https://www.cs.dartmouth.edu/~doug/powser.html.

Doug _______________________________________________ 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.