Как умножить два полиномиальных списка в схеме

Question

Я ищу советы о том, как умножить два полиномиальных списка, например, как создать функцию (poly_mul '(3 4 5)' (5 9 6 2)), результат должен быть (15 47 79 75 38 10)

Что у меня до сих пор:

(define (poly-mul lst1 lst2)
(let loop ((expo 0) (l1 lst1) (l2 lst2))
(cond ((null? l1) '())
      ((null? l2) (loop expo (cdr l1) lst2))
      (else (cons (* (car l1) (car l2))
                  (loop expo l1 (cdr l2)))))))

Answer 1

Вы можете посмотреть на poly-mult как на рекурсив poly-add.Учитывая простоту реализации poly-add.

(define (poly-add p1 p2)
  (cond ((empty? p1)
         p2)
        ((empty? p2)
         p1)
        (else
         (cons (+ (car p1)
                  (car p2))
               (poly-add (cdr p1)
                         (cdr p2))))))

Вы можете реализовать poly-mult таким образом, используя вспомогательную процедуру, raise.

(define (poly-mul p1 p2 (e 0))
  (if (empty? p1)
      empty
      (poly-add (raise e (map (curry * (car p1)) p2))
                (poly-mul (cdr p1)
                          p2
                          (+ e 1)))))

(define (raise e p)
  (if (= e 0)
      p
      (cons 0
            (raise (- e 1)
                   p))))

(poly-mul '(3 4 5) '(5 9 6 2))
;; '(15 47 79 75 38 10)

Определив raise в качестве внешней процедуры легко увидеть, как мы поднимаем многочлены до следующей степени.Тем не менее, мы могли бы сохранить это поведение внутри poly-mult, используя цикл и превращая экспоненту (e) в саму функцию.

(define (poly-mul p1 p2)
  (let loop ((p p1)         ;; polynomial
             (e identity))  ;; exponent
    (if (empty? p)
        empty
        (poly-add (e (map (curry * (car p)) p2))
                  (loop (cdr p)
                        (compose (curry cons 0) e))))))

(poly-mul '(3 4 5) '(5 9 6 2))
;; '(15 47 79 75 38 10)

Наконец, использование цикла в poly-mult облегчаетдля нас, чтобы преобразовать рекурсивный вызов в правильный хвостовой вызов.Операция poly-add теперь выполняется первой, а обновленный аккумулятор (acc) передается следующей итерации цикла.

(define (poly-mul p1 p2)
  (let loop ((acc empty)   ;; accumulator
             (p p1)        ;; polynomial
             (e identity)) ;; exponent
    (if (empty? p)
        acc
        (loop (poly-add acc
                        (e (map (curry * (car p)) p2)))
              (cdr p)
              (compose (curry cons 0) e)))))

Answer 2

С SRFI-1 fold-right это цикл масштабирования, сдвига и добавления справа, как и в математике средней школы:

(require srfi/1)

(define (multpoly p1 p2)
  (fold-right
      (lambda (a r)
         (addpoly (map (lambda (b) (* a b)) p2)  ; map (a*) p
                  (cons 0 r)))
      '() p1))

где

(define (addpoly p1 p2)
  (cond ((null? p1) p2)
        ((null? p2) p1)
        (else (cons (+       (car p1) (car p2))
                    (addpoly (cdr p1) (cdr p2))))))

Answer 3

Вы нашли способ умножения чисел.Теперь вам нужно добавить их со смещенными индексами, как на бумаге:

 15 27 18 06 00 00
 00 20 36 24 08 00
 00 00 25 45 30 10

Было бы намного проще работать с векторами, со списком вы можете, например, добавлять нули по мере суммирования:

(define polynomial-mul
  (lambda (lst1 lst2)    
    (let ((tmp 
           (map (lambda (n) 
              (map (lambda (m) 
                     (* n m)) 
                   lst2)) lst1)))
      (let loop ((z '(0)) (l (car tmp)) (r (cdr tmp)))
        (cond
         ((null? r) l)
         (else
          (loop (cons 0 z) 
                (map + 
                     (append l '(0))
                     (append z (car r)))
                (cdr r))))))))            

Но это очень неэффективно из-за добавления.Для сдвига двух списков лучше использовать вспомогательную функцию:

(define shifted-map
  (lambda (f shift lst1 lst2)
    (cond
     ((and (not (null? lst1)) (not (zero? shift))) 
      (cons (car lst1) 
            (shifted-map f (sub1 shift) (cdr lst1) lst2)))
     ((null? lst2) lst1)
     (else
      (cons (f (car lst1) (car lst2))
            (shifted-map f shift (cdr lst1) (cdr lst2)))))))

(define polynomial-mul
  (lambda (lst1 lst2)    
    (let ((tmp 
           (map (lambda (n) 
              (map (lambda (m) 
                     (* n m)) 
                   lst2)) lst1)))
      (let loop ((shift 1) (l (car tmp)) (r (cdr tmp)))
        (cond
         ((null? r) l)
         (else
          (loop  
           (add1 shift)
           (shifted-map + shift l (car r))
           (cdr r))))))))