Power serious: explanations

Here we explain some of the less obvious one-liners on the power serious page.

Coercion

Coercion lets us use a scalar in place of an infinite series, e.g. 1 instead of [1,0,0,...].

A crucial bit of Haskell magic is that constants are polymorphic: the type of an integer constant is Num a => a. In expressions like xs+1, the constant takes on whatever type is needed to make both operands have the same type. This is done by implicitly invoking the standard function 

   fromInteger :: Num a => Integer -> a
which converts integers to other types. fromInteger belongs to type class Num, along with arithmetic operations + - *. The definition for converting to power series is 
   fromInteger c = series(fromInteger c)  -- promote constants
Here fromInteger::Num a=>Integer->[a] on the left is defined in terms of fromInteger::Num a=>Integer->a on the right, which indicates that constant c must be coerced to the required type of list element before series is applied to make a list. This definition occurs as part of an instance declaration that places lists of numeric values in class Num; see the bare-bones package.

Note. The previous formula can be stated in "pointless" form: 

   fromInteger = series . fromInteger

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 + xF'(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 it 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 elegant, 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 imjects 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 have been described by enumeration. The reminder is heavy-handed: int pascal becomes a type error because the coefficents in pascal are power series. This could be fixed by throwing power series into class Enum (as Haskell does with rationals) or by eliminating enumerations from the program. The practical package takes the latter, gentler, alternative.

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.

The [0] in 

   pascal = 1/(1 - [[0],[1,1]])
arises because (1+x)z represented as a power series in z is 0z0 + (1+x)z1. The [0] could be simplified to [].