Power serious: explanations

Coercion

Coercion promotes a scalar such as 2 to a power series [2,0,0,...]. This allows us to write expressions like 2*sins, where sins is a power series, without violating Haskell's requirement that both operands of * have the same type.

Haskell implicitly applies a coercion function, frominteger, to integer constants. We supply a definition of frominteger that tells how to promote integers to power series.

frominteger belongs to type class Num, along with the usual arithmetic operations + − *. We place power series, represented as lists of numerics, in this class by a declaration that reads in part 

   instance (Num a, Eq a) => Num [a] where
      fromInteger c = series(fromInteger c)
This places type [a], i.e. lists with elements of type a, in class Num, on the condition that type a itself is in class Num.

A new instance of fromInteger with type Num a=>Integer−>[a] is defined in terms of an old instance with type Num a=>Integer−>a. This arranges for c to be presented in the type required for list elements, typically Integer or Rational.

Negation

Haskell's standard name for unary negation is negate, but it can be written as − in expressions.

Multiplication

If F and G are two power series, with first terms f and g and tails F' and G', such that

    F(x) = f + xF'(x)
    G(x) = g + xG'(x)

then their product is given by

    fg + x(F')(g + xG') + xfG'

which translates straightforwardly to 

    (f:ft) * gs@(g:gt) = f*g : ft*gs + series(f)*gt
Because the signature of (*) is Num a=>a−>a−>a, we cannot use (*) for mixed-type multiplication; hence the coercion with series. When finite series are admitted, as in the practical package, fG' may be realized as [f]*gt.

Note. A more efficient, less transparent, realization of fG' is map (f*) gt.

Division

If Q is the quotient of series F and G, we have

    F = f+xF' = QG = (q+xQ')(g+xG')

from which we see that f = qg and F' = (q+xQ')G' + Q'g = QG' + Q'g, and finally that

    Q = q+xQ' = f /g + x(1/g)(F' − QG')

Long division in a nutshell!

Composition

The composition of F(x) and G(x) is F(G(x)), which expands to

    f + (g+xG')F'(G)

The first term of F(G) is f+gF'(g), which is an infinite sum unless F is a finite series (i.e. a polynomial). Thus for safety we require g=0. The composition formula becomes

    F(G(x)) = f + xG'F'(G)

Reversion

Reversion is the process of computing the compositional inverse of power series F(x).
The inverse R satisfies F(R(x)) = x, which expands to

    f + (r+xR')(F'(R)) = x

For the composition F'(R) to work, we must have r=0, which implies that f=0.
Solving for R' gives

    R' = 1/F'(R)

Integration and differentiation

The use of an enumeration, [1..], in the definitions 
   int fs = 0 : zipWith (/) fs [1..]
   diff (_:ft) = zipWith (*) ft [1..]
is pretty, but not ideal, for it injects class Enum into the type contexts: 
   int :: (Fractional a, Enum a) => [a] −> [a]
   diff :: (Num a, Enum a) => [a] −> [a]
Enum in the type reminds us that these operations combine coefficients with term indexes, which happen to be specified as arithmetic sequences, thereby imposing the Enum constraint. The reminder is heavy-handed; int pascal becomes a type error because the coefficents in pascal are lists, in class Num but not in class Enum. The trouble could be fixed by throwing power series into class Enum (as Haskell rather cavalierly does with rationals) or by eschewing arithmetic-sequence notation. Having originally done the latter, the practical package now takes a third way: map fromInteger over the list [1..] to yield the desired type, Num a => [a].

Examples

Typechecking the formula 
   tans = revert(int(1/(1:0:1)))
reveals that (1:0:1) must be a list. As the right operand of (:) is a list, the final 1 must be a list, so it gets coerced to a series. We can replace (1:0:1) by [1,0,1] only when using a power series package equipped to handle finite lists.

Note. This definition is clever, but tans = sins/coss is simpler and faster.

In the definition of pascal 

   1/[1, −[1,1]]
represents 1/(1z0 − (1x0+1x1)z1). Automatic coercion converts it to an ungainly form: 
   [[1]]/[[1], −[1,1]]