Utiliser une voiture imbriquée avec des inconvénients dans une fonction lisp

L'idée générale va dans la bonne direction. Il y a cependant un tas de problèmes. Jetons un œil.

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

Premier retrait:

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

Parenthèses pendantes suivantes:

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

Retourne la liste vide en IF pour le cas vrai:

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

Maintenant contre le résultat dans le cas faux :

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

Que reste-t-il à faire?

• voir le commentaire par 'rsm': remplacez le devis par un appel à list .
• n'utilisez pas list-length . Utilisez plutôt null . Il vérifie si une liste est vide. list-length traverserait les listes entières d'entrée à chaque appel -> inefficace.

Si vous appelez list-length à chaque étape de récursivité, vous allez parcourir les deux listes entièrement à chaque fois, ce qui donne à votre fonction zipper une complexité temporelle quadratique avec par rapport à la somme des tailles de vos listes:

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

Ceci est inefficace et pas nécessaire ici. Puisque vous visitez déjà les deux listes, vous pouvez directement vérifier si l'une d'entre elles est vide en utilisant null ou endp , qui prennent un temps constant. Vous renvoyez NIL dès que l'une des listes est vide, ce qui est d'ailleurs le comportement par défaut de mapcar . Notez également que mapcar peut fonctionner sur plusieurs listes en même temps, par exemple:

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

...

Si vous connaissez une fonction qui prend (au moins) deux arguments et renvoyer une liste, alors vous pouvez mapcar cette fonction sur vos listes et avoir une liste de listes.

La fonction zip d'autres langages tels que Python et Haskell est un cas particulier de mapcar .

La fonction traditionnelle zip peut être réalisée via:

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

Tel que pour ce cas:

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

Fonction

zip avec un nombre arbitraire de listes

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

La liste la plus courte détermine la profondeur de la compression.

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

Vous pouvez faire quelque chose comme ceci:

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

Nous pouvons vérifier si l'une des listes est nulle, afin que nous puissions nous arrêter quand l'une des listes est épuisée (comme mapcar cessera d'appliquer une fonction aux listes lorsque l'une des listes sera épuisée). On peut alors comparer une liste imbriquée avec les voitures des listes dans chaque appel récursif. Votre sortie serait:

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

Nous pourrions également utiliser mapcar car il itérera sur les deux listes et retournera le résultat de l'application de la fonction aux deux listes (contrairement à mapc). Il s'agit de moins de lignes de code, et comme il reviendra quand une liste sera épuisée, il n'y a pas besoin de conditionnel:

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