4 ms·

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)

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 https://dl.acm.org/doi/abs/10.1017/s0956796899003299)

svat 1y ago
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]

svat 1y ago

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]