Series are represented as lists of numeric coefficients

and are understood formally; convergence is not an issue.

Because the lists are unbounded in length, lazy evaluation is essential.

Extra rules for empty lists will make the operations
work also on

finite-length inputs (polynomials)
and allow coerced scalars to be finite series.

Reference:
M. D. McIlroy, The music of streams (.ps.gz),

Information Processing Letters **77** (2001) 189-195.

An explanation page elucidates some details of formulas marked as links.

series f = f : repeat 0 fromInteger c = series(fromInteger c) -- promote constants

negate (f:ft) = -f : -ft

(f:ft) + (g:gt) = f+g : ft+gt

(f:ft) * gs@(g:gt) = f*g : ft*gs + series(f)*gt

(f:ft) / (g:gt) = qs where qs = f/g : series(1/g)*(ft-qs*gt)

subtraction in terms of addition and negation,

reciprocation (

nonnegative integer power (^) in terms of multiplication, and

and general integer power (^^) in terms of (^)reciprocation.

(f:ft) # gs@(0:gt) = f : gt*(ft#gs)

revert (0:ft) = rs where rs = 0 : 1/(ft#rs)

int fs = 0 : zipWith (/) fs [1..] -- integral from 0 to x

diff (_:ft) = zipWith (*) ft [1..] -- type (Num a,Enum a)=>[a]->[a]

Thus 1+

series for tan

tans = revert(int(1/(1:0:1)))From the usual differential relations between sine and cosine follows code

to compute their power series. Lazy evaluation enables the mutual recursion.

sins = int coss coss = 1 - int sinsWhen the operations are generalized to keep polynomials finite, the coefficients

of power series can themselves be (finite) power series. Then the identity

1/(1−(1+

pascal = 1/[1, -[1,1]]This formula expands to a list of lists:

[[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1], ...]::[[Rational]]

For a quick test, try

(Sorry, package file extensions are .txt to placate some browsers.)

Extensions to handle polynomials make a
practical package, doubled in size,

not as pretty, but much faster and capable of feats like `pascal`.

To see the dramatic speedup,
try a bigger test like `take 20 tans`.

Why is finite more complicated than infinite? The end must be detected, if nothing else.

doug@cs.dartmouth.edu

July 2007

Aug 2007. Text, but not code, trivially modified.

Sep 2007. Misprint in definition of `sins` corrected; OK in the complete packages.

Explanation page and Pascal's triangle added. Minor text modifications.

Mar 2008. Tweak the introduction.

Apr 2008.
Link code to explanations.

Change certain hyphens to minus signs.
Explain and fix
Enum nuisance.

Jul 2008. Trivial text edits.

Sep 2009. Mention operator (^^).
Shortcut multiplication by 0 in practical package.

Oct 2009. Mention `recip`.

Apr 2012. Page translated to Romanian by Alexandra Seremina.

Mar 2013. Correct a typo in explanations.

Nov 2013. Simplified definition of `pascal`. Tweaked typesetting
of formulas in explanations.

Dec 2013. Replace package file extensions .hs by .txt.

Feb 2014. Show the expansion of `pascal`.