structure SparsePoly : PolySig =
struct
type Poly = {coeff:real, power:int} list
(* keep lists in order of increasing powers *)

fun a ++ [] = a :Poly
  | [] ++ b = b
  | (poly1 as ((h1 as {coeff = c1, power = p1}) :: t1))
    ++
    (poly2 as ((h2 as {coeff = c2, power = p2}) :: t2))
    = if p1 = p2 then {coeff = c1 + c2, power = p1} :: (t1 ++ t2)
      else if p1 < p2 then h1 :: (t1 ++ poly2)
      else (* p2 < p1 *)   h2 :: (poly1 ++ t2)


fun times _ [] = [] :Poly
  | times (term as {coeff = c, power = p}) ({coeff = ch, power = ph} :: t)
        = {coeff = c * ch, power = p + ph} :: times term t

fun [] ** x  = [] :Poly
  | x  ** [] = []
  | (a :: aa) ** bb = (times a bb) ++ (aa ** bb)

infix 9 ^^;
fun a ^^ 0 = 1.0
  | a ^^ n = if n mod 2 = 0 then (a*a) ^^ (n div 2)
                            else (a*a) ^^ (n div 2) * a
fun eval []        v = 0.0
  | eval ({coeff, power} :: aa) v = (coeff * (v ^^ power)) + (eval aa v)

fun diff [] = [] 
  | diff ({coeff, power} :: t) = 
         if power < 1 then diff t
         else {coeff = coeff * real power, power = power - 1} :: diff t

fun intterm {coeff, power} = {coeff = coeff/real(power + 1), power = power + 1}

fun int x = map intterm x ;
end;