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

[Vanessa McHale]

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 <vamchale at gmail.com> 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 <douglas.mcilroy at dartmouth.edu> 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.
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20250210/9b7e19ae/attachment.html>