--* From bmt@spadserv.watson.ibm.com  Fri Jan 22 07:46:50 1993
--* Received: from spadserv.watson.ibm.com by radical.watson.ibm.com (AIX 3.2/UCB 5.64/900524)
--*           id AA11167; Fri, 22 Jan 1993 07:46:50 -0500
--* Received: by spadserv.watson.ibm.com (AIX 3.2/UCB 5.64/900524)
--*           id AA19270; Fri, 22 Jan 1993 07:46:01 -0500
--* Date: Fri, 22 Jan 1993 07:46:01 -0500
--* From: bmt@spadserv.watson.ibm.com
--* X-External-Networks: yes
--* Message-Id: <9301221246.AA19270@spadserv.watson.ibm.com>
--* To: axc-bug@radical.watson.ibm.com
--* Subject: 4 meanings for Record ???? 25.3

--@ Fixed  by: SMW Sat Oct 09 15:17:07 1993
--@ Tested by: <name of new or existing file in test directory>
--@ Summary:   <One line description of real problem and the fix>


#include "aslib.as"

Expon ==> SingleInteger
^= ==> ~=   
null ==> empty?

Polynomial(S: Ring): Ring with
               var: Expon -> %
               * : (S, %) -> %
               * : (%, S) -> %
               degree: % -> Expon
               ^ : (%, Expon) -> %

  == add

    Term ==> Record(coef:S, expon:Expon)
    Rep ==> List Term
    import Term
    import Rep

    0:% == per nil
    var(n:Expon):% == per cons([1@S,n],nil)
    degree(x:%):Expon ==
       empty? rep x => 0
       first(rep x).expon
    (- x:%): % == per [[-t.coef,t.expon] for t in rep x]
    (xx:% + yy:%): % ==
          x := rep xx
          y := rep yy
          null x => yy
          null y => xx
          first(y).expon > first(x).expon =>
             per cons(first y,rep(xx + per rest y))
          first(x).expon > first(y).expon =>
             per cons(first x,rep(per rest x + yy))
          r:= first(x).coef + first(y).coef
          r = 0 => per rest x + per rest y
          per cons([first(x).expon,r],rep(rest x + rest y))

    (xx:% - yy:%): % ==
          x := rep xx
          y := rep yy
          null x => - yy
          null y => xx
          first(y).expon > first(x).expon =>
             per cons([first(y).expon,-first(y).coef],rep(xx - per rest y))
          first(x).expon > first(y).expon =>
             per cons(first x,rep(per rest x - yy))
          r:= first(x).coef - first(y).coef
          r = 0 => per rest x - per rest y
          per cons([first(x).expon,r],rep(rest x - rest y))

    (c:S * x:%): % ==
          c = 0 => 0
          c = 1 => x
          per [[u.expon,a] for u in rep x | (a:=c*u.coef) ^= 0]
    (x:% * c:S): % ==
          c = 0 => 0
          c = 1 => x
          per [[u.expon,a] for u in rep x | (a:=u.coef*c) ^= 0]

    (x:% * y:%): % ==
          p1 := rep x
          p2 := rep y
          empty? p1 => p1
          empty? p2 => p2
          first(p1).expon = 0 => first(p1).coef * p2
          first(p2).expon = 0 => p1 * first(p2).coef
          prod :% := 0
          for m in reverse(p1) repeat prod := prod + m*y
          prod
    (m:Term * y:%): % == 
          [[m.expon+t2.expon,r] for t2 in rep y | (r:=m.coef*t2.coef) ^= 0]