[vmchale]

in Haskell you can read off the generating function's coefficients directly from the functional equation T(z) = z + zT + zT² + zT²

ghci> ts=0:(1+ts+ts^2+ts^3) ghci> take 12 ts [0,1,1,2,5,13,36,104,309,939,2905,9118]

Using the Num instance for power series (very cute application of laziness expounded by Karczmarczuk and then McIlroy https://dl.acm.org/doi/abs/10.1017/s0956796899003299)

[svat]

This is cool! What does one need to do to get this to work? I get:

    $ ghci
    GHCi, version 9.12.2: https://www.haskell.org/ghc/  :? for help
    ghci> ts=0:(1+ts+ts^2+ts^3)
    ghci> take 12 ts
    <interactive>:2:1: error: [GHC-39999]
        • No instance for ‘Num [Integer]’ arising from a use of ‘it’
        • In the first argument of ‘print’, namely ‘it’
          In a stmt of an interactive GHCi command: print it

Edit: After reading Bentley's paper that you linked, figured it out:

    $ cat > bentley.hs
    ps0:: Num a => [a]
    ps0 = 0 : ps0

    -- (.*):: Num a => a->[a]->[a]
    c .* (f:fs) = c*f : c.*fs

    instance Num a => Num [a] where
        -- negate (f:fs) = (negate f) : (negate fs)
        (f:fs) + (g:gs) = f+g : fs+gs
        (f:fs) * (g:gs) = f*g : (f.*gs + fs*(g:gs))
        fromInteger c = fromInteger c : ps0

    ^D
    $ ghci bentley.hs
    GHCi, version 9.12.2: https://www.haskell.org/ghc/  :? for help
    [1 of 2] Compiling Main             ( bentley.hs, interpreted )
    bentley.hs:7:10: warning: [GHC-06201] [-Wmissing-methods]
        • No explicit implementation for
            ‘abs’, ‘signum’, and (either ‘negate’ or ‘-’)
        • In the instance declaration for ‘Num [a]’
    |
    7 | instance Num a => Num [a] where
    |          ^^^^^^^^^^^^^^^^

    Ok, one module loaded.
    ghci> ts=0:(1+ts+ts^2+ts^3)
    ghci> take 12 ts
    [0,1,1,2,5,13,36,104,309,939,2905,9118]