fact: Fixpoint poly_add pl {struct pl} := match pl with | Cst cl => fix F pr := match pr with | Cst cr => Cst (xorb cl cr) | Poly pr ir qr => Poly (F pr) ir qr end | Poly pl il ql => fix F pr {struct pr} := match pr with | Cst cr => Poly (poly_add pl pr) il ql | Poly pr ir qr => match Pos.compare il ir with | Eq => let qs := poly_add ql qr in if decide (null qs) then poly_add pl pr else Poly (poly_add pl pr) il qs | Gt => Poly (poly_add pl (Poly pr ir qr)) il ql | Lt => Poly (F pr) ir qr end end end.
imports: Bool PArith DecidableClass Ring Lia