{- Basic operations on power series and polynomials
represented by lists, practical version, as described
in http://www.cs.dartmouth.edu/~doug/powser.html
Doug McIlroy, July 2007
-}
default (Integer,Rational,Double)
infixr 9 #
instance (Num a, Eq a) => Num [a] where
fromInteger c = [fromInteger c]
negate fs = map negate fs
(f:ft) + (g:gt) = f+g : ft+gt
fs + [] = fs
[] + gs = gs
(0:ft) * gs = 0 : ft*gs -- caveat: 0*diverge = 0
fs * (0:gt) = 0 : fs*gt
(f:ft) * gs@(g:gt) = f*g : ft*gs + [f]*gt
_ * _ = []
instance (Fractional a, Eq a) => Fractional [a] where
fromRational c = [fromRational c]
(0:ft) / gs@(0:gt) = ft/gt
(0:ft) / gs@(g:gt) = 0 : ft/gs
(f:ft) / gs@(g:gt) = f/g : (ft-[f/g]*gt)/gs
[] / (0:gt) = []/gt
[] / (g:gt) = []
_ / _ = error "improper power series division"
(f:ft) # gs@(0:gt) = f : gt*(ft#gs)
(f:ft) # gs@(g:gt) = [f] + gs*(ft#gs) -- ft must be polynomial
[] # _ = []
(f:_) # [] = [f]
revert (_:0:_) = error "revert f where f'(0)==0"
revert (0:ft) = rs where rs = 0 : 1/(ft#rs)
revert [f,f'] = [-f/f',1/f']
revert _ = error "revert f where f(0)/=0"
int fs = 0 : zipWith (/) fs (map fromInteger [1..])
diff (_:ft) = zipWith (*) ft (map fromInteger [1..])
tans = revert(int(1/(1:0:1)))
sins = int coss
coss = 1 - int sins
pascal = 1/[1, -[1,1]]