Пример алгоритма умножения полиномов от одной переменной и его реализация

В книге "Компьютерная алгебра: системы и алгоритмы алгебраических вычислений" (авторы: Дж. Дэвенпорт, И. Сирэ, Э. Турнье) представлены примеры реализации на Lisp'е алгоритмов сложения и умножения полиномов от одной переменной. Полином здесь представляется списком элементов типа CONS (s-выражение). Элементы этого списка представляют мономы:
$(\lt power\gt\ .\ \lt coefficient\gt)$. Списки предполагаются отсортированными по убыванию степени (старшая степень у головы списка), и каждый моном в списке имеет свою уникальную (в пределах списка, конечно) степень. Таким образом, полином $3x^2+1$ представляется списком ((2 . 3) (0 . 1)).

Код этих примеров, перенесённый на Common Lisp:

(defun add-poly (a b)
    "Adds two polynomials"
    (cond ((null a) 
              b
          )
          ((null b)
              a
          )
          ((> (caar a) (caar b))
              (cons (car a) (add-poly (cdr a) b))
          )
          ((< (caar a) (caar b))
              (cons (car b) (add-poly a (cdr b)))
          )
          ((zerop (+ (cdar a) (cdar b)))
              (add-poly (cdr a) (cdr b))
          )
          (t
              (cons
                  (cons (caar a)) (+ (cdar a) (cdar b))
                  (add-poly (cdr a) (cdr b))
              )
          )
    )
)

(defun multiply-poly (a b)
    "Multiplies two polynomials"
    (cond ((or (null a) (null b))
              nil
          )
          (t
              (cons
                  (cons (+ (caar a) (caar b)) (* (cdar a) (cdar b)))
                  (add-poly (multiply-poly (list (car a)) (cdr b))
                            (multiply-poly (cdr a) b)
                  )
              )
              
          )
    )
)

Пример вызова функции:

(multiply-poly '((17 . 2) (3 . 4)) '((19 . 4) (3 . 5) (2 . 2)))

Вывод

((36 . 8) (22 . 16) (20 . 10) (19 . 4) (6 . 20) (5 . 8))

И ещё пример реализации этих алгоритмов на языке Haskell для целочисленных коэффициентов. Здесь полином представляется списком кортежей $(\lt power\gt,\ \lt coefficient\gt)$.

addPoly :: [(Integer, Integer)] -> [(Integer, Integer)] -> [(Integer, Integer)]
addPoly [] b = b
addPoly a [] = a
addPoly a@(aLeadMonomial@(aLeadMonDegree, aLeadMonCoeff):aRestMonomials)
        b@(bLeadMonomial@(bLeadMonDegree, bLeadMonCoeff):bRestMonomials)
    | aLeadMonDegree > bLeadMonDegree       = aLeadMonomial : (addPoly aRestMonomials b)
    | bLeadMonDegree > aLeadMonDegree       = bLeadMonomial : (addPoly bRestMonomials a)
    | leadCoeffsSum == 0  = restMonomialsSum
    | otherwise = (aLeadMonDegree, leadCoeffsSum) : restMonomialsSum
    where leadCoeffsSum = aLeadMonCoeff + bLeadMonCoeff
          restMonomialsSum = addPoly aRestMonomials bRestMonomials


multiplyPoly :: [(Integer, Integer)] -> [(Integer, Integer)] -> [(Integer, Integer)]
multiplyPoly _ [] = []
multiplyPoly [] _ = []
multiplyPoly (aLeadMonomial@(aLeadMonDegree, aLeadMonCoeff):aRestMonomials)
             b@(bLeadMonomial@(bLeadMonDegree, bLeadMonCoeff):bRestMonomials) =
             (aLeadMonDegree + bLeadMonDegree, aLeadMonCoeff * bLeadMonCoeff) :
                addPoly (multiplyPoly [aLeadMonomial] bRestMonomials)
                        (multiplyPoly aRestMonomials b)

Пример вызова функции:

 multiplyPoly [(17, 2), (3, 4)] [(19, 4), (3,5), (2,2)]

Вывод

[(36,8),(22,16),(20,10),(19,4),(6,20),(5,8)]