Использование вложенной машины с минусами в функции lisp

Question

Я делаю рекурсивную функцию lisp, которая берет два списка и создает подсписок пар индекса

например: положить (A B C D) и (1 2 3 4) и получить ((1 A) (2 B) (3 C) (4 D))

Тем не менее, у меня возникли проблемы с использованием автомобиля вместе с минусами, чтобы сделать указанный список. Вот мой код:

(DEFUN zipper (a b)
    (if (= (OR (list-length a) (list-length b)) 0)
        (setq c NIL)
        (progn (zipper (cdr a) (cdr b))
        (cons '((car a) (car b)) c))
    )
)

Я немного поиграл, и кажется, что использование машины для создания списков не работает большую часть времени. Кроме того, я использую CLISP. Есть идеи?

Спасибо!

Answer 1

Общая идея идет в правильном направлении. Хотя есть куча проблем. Давайте посмотрим.

(DEFUN zipper (a b)
    (if (= (OR (list-length a) (list-length b)) 0)
        (setq c NIL)
        (progn (zipper (cdr a) (cdr b))
        (cons '((car a) (car b)) c))
    )
)

Первый отступ:

(DEFUN zipper (a b)
  (if (= (OR (list-length a) (list-length b)) 0)
      (setq c NIL)
      (progn (zipper (cdr a) (cdr b))
        (cons '((car a) (car b)) c))                 ; <--
    )
  )

Следующие висячие скобки:

(DEFUN zipper (a b)
  (if (= (OR (list-length a) (list-length b)) 0)
      (setq c NIL)
      (progn (zipper (cdr a) (cdr b))
        (cons '((car a) (car b)) c))))

Верните пустой список в IF для истинного случая:

(defun zipper (a b)
  (if (= (OR (list-length a) (list-length b)) 0)
      nil
      (progn (zipper (cdr a) (cdr b))
        (cons '((car a) (car b)) c))))

Теперь минусы с результатом в ложном случае:

(defun zipper (a b)
  (if (= (OR (list-length a) (list-length b)) 0)
      nil
      (cons '((car a) (car b))
            (zipper (cdr a) (cdr b)))))

Что еще предстоит сделать?

• см. комментарий к rsm: замените цитату вызовом list,
• не использовать list-length, использование null вместо. Он проверяет, является ли список пустым. list-length будет проходить входные целые списки при каждом вызове -> неэффективно.

Answer 2

Если вы позвоните list-length на каждом этапе рекурсии вы будете проходить оба списка полностью каждый раз, что дает zipper Функция квадратичной временной сложности по отношению к сумме размеров ваших списков:

(zipper '(1 2 3) '(4 5 6))
=> (list-length (1 2 3))
=> (list-length (2 3))
=> (list-length (3))
=> (list-length ())

=> (list-length (4 5 6))
=> (list-length (4 5))
=> (list-length (5))
=> (list-length ())

(zipper '(2 3) '(5 6))
=> (list-length (2 3))
   ...
=> (list-length (5 6))
   ...

...

Это неэффективно и не нужно здесь. Поскольку вы уже посещаете оба списка, вы можете напрямую проверить, является ли какой-либо из них пустым, используя null или же endp, которые занимают постоянное время. Вы возвращаете NIL, как только один из списков пуст, что, кстати, является поведением по умолчанию mapcar, Обратите внимание также, что mapcar может работать с несколькими списками одновременно, например:

(mapcar #'+ '(1 2) '(5 8))
=> (6 10)

Если вы знаете функцию, которая принимает (как минимум) два аргумента и возвращает список, то вы можете mapcar эта функция над списками и список списков.

Answer 3

zip функция из других языков, таких как Python и Haskell, является частным случаем mapcar,

Традиционный zip Функция может быть достигнута через:

> (mapcar #'list list1 list2 ... listn)

Такой, что для этого случая:

> (mapcar #'list '(A B C D) '(1 2 3 4))
((A 1) (B 2) (C 3) (D 4))

Чтобы поменять порядок пар, как вы указали, просто измените переданную функцию на mapcar соответственно:

> (mapcar #'(lambda (x y) (list y x)) '(A B C D) '(1 2 3 4))
((1 A) (2 B) (3 C) (4 D))

Ознакомьтесь с документацией для mapcar для более подробной информации.

Answer 4

zipфункция с произвольным количеством списков

(defun zip (&rest lists)
  (apply #'mapcar #'list lists))

Кратчайший список определяет глубину архивирования.

CL-USER> (zip '(1 2 3) '(a b c) '("a" "b" "c"))
((1 A "a") (2 B "b") (3 C "c"))
CL-USER> (zip '(1 2 3) '(a b c) '("a" "b" "c" "d"))
((1 A "a") (2 B "b") (3 C "c"))

Answer 5

Вы можете сделать что-то вроде этого:

(defun zipper (a b)
   (if (or (null a) (null b))
       nil
       (cons (list (car b) (car a)) (our-combiner (cdr a) (cdr b)))))

Мы можем проверить, является ли один из списков нулевым, чтобы мы могли остановиться, когда закончится один из списков (аналогично тому, как mapcar перестанет применять функцию к спискам, когда закончится один из списков). Затем мы можем объединить вложенный список со списком машин в каждом рекурсивном вызове. Ваш вывод будет:

CL-USER> (zipper '(a b c d) '(1 2 3 4))
((1 A) (2 B) (3 C) (4 D))
CL-USER> 

Мы также можем использовать mapcar, поскольку он будет перебирать оба списка и возвращать результат применения функции к обоим спискам (в отличие от mapc). Это меньше строк кода, и поскольку он вернется, когда закончится какой-то список, нет необходимости в условном выражении:

(defun zipper (a b)
  (mapcar #'list b a))