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

Question

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

ex: положить в (ABCD) и (1 2 3 4) и получить ((1A) (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 (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))

Answer 2

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 3

Если вы вызываете 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 4

Функция 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 5

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

(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))))

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

(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 будет обходить входные целые списки при каждом вызове -> неэффективно.