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 power series coefficients, 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. Hence Q′ = F′ − (1/g)QG′ and

    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 plus the first term of gF′(G). The first term of F′(G) expands similarly, and so on to an infinite sum. To forestall divergent computation, we require g=0. The composition formula becomes

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

Reversion


The compositional 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, whence 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 its coefficents are lists, which are in class Num but not in class Enum. The trouble could be fixed by arbitrarily throwing power series into class Enum 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

The last 1 in 
   tans = revert(int(1/(1:0:1)))
gets coerced to series 1. The more general practical package allows us to use the more efficient polynomial [1:0:1] in place of the infinite series (1:0:1).

Note. The definition of tans 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 
   [[1]]/[[1], −[1,1]]