Блог

Главная - Вопросы по программированию - Напишите рекурсивную функцию LISP, которая находит скалярное произведение двух списков чисел одинаковой длины

Напишите рекурсивную функцию LISP, которая находит скалярное произведение двух списков чисел одинаковой длины

#recursion #lisp #common-lisp

#рекурсия #lisp #common-lisp

Вопрос:

Только начал изучать LISP, и я пытаюсь понять, как написать следующую рекурсивную функцию.

Итак, я должен иметь 

 (DOT-PRODUCT '(1 2) '(3 4)))

Результат должен быть 11

Я написал следующее 

 (defun DOT-PRODUCT (a b)
  (if (or (null a) (null b))
      0
      (  (* (first a) (first b))
         (DOT-PRODUCT (rest a) (rest b)))))

И, похоже, все работает; однако, он по-прежнему работает со списками разной длины. Я хочу, чтобы он просто работал со списками чисел одинаковой длины. Куда я должен добавить код, который возвращает «недопустимую длину», если у нас есть такой?

Ответ №1:

Простой способ — переписать функцию так, чтобы она проверяла разные случаи, используя условную форму cond :

 (defun dot-product (a b)
  (cond ((null a) (if (null b) 0 (error "invalid length")))
        ((null b) (error "invalid length"))
        (t (  (* (first a) (first b))
              (dot-product (rest a) (rest b))))))

В первой ветви cond , если первый аргумент равен NIL , второй тоже должен быть NIL , иначе генерируется ошибка. Во второй ветви мы уже знаем, что a это не NIL так, поэтому немедленно генерируется ошибка. Наконец, результат вычисляется.

Комментарии:

1. Спасибо за подробное объяснение и предложение по использованию cond вместо if . Это действительно помогает!

Ответ №2:

Умножьте соответствующие элементы списков X и Y:

 (mapcar #'* X Y)

Добавьте элементы списка Z:

 (reduce #'  Z)

В совокупности: скалярное произведение:

 (reduce #'  (mapcar #'* X Y))

reduce и mapcar являются основой концепции «MapReduce«, которая является обобщением такого рода вещей, которые включают скалярные произведения, интегралы свертки и множество способов массирования и обобщения данных.

Ответ №3:

Можно повысить эффективность, введя накопительную переменную и превратив стандартную рекурсию в хвостовую рекурсию. В этом примере я использовал (labels) для определения рекурсии:

 (defun DOT-PRODUCT (a b)
  (labels ((dp (x y accum)
             (if (or (null x) (null y))
                 accum
                 (dp (rest x) (rest y) (  accum (* (first x) (first y)))))))
    (if (= (length a) (length b))
        (dp a b 0)
        (error "Invalid length."))))