Présentation d'une liste

Question

J'ai cette liste des noms et des langues différentes

(setq l '((david spanish german) 
      (amanda italian spanish english) 
      (tom german french))) 

Je veux faire l'autre avec une fonction: pour chaque langue, j'ai besoin de tous les noms relationed avec toutes les langues.

Par exemple, si je l'appelle la fonction avec la liste L:

(lenguages L) 

Je veux montrer ceci:

((english (amanda)) 
    (spanish (david amanda)) 
    (italian (amanda)) 
    (german(david tom)) 
    (french(tom)) 
) 

J'ai une idée de la façon de le faire, mais il montre juste un article.

(defun lenguages(names) 
    (cond((null names) nil) 
    ((list (cadar names) (list (caar names)))))) 

cette dernière fonction ne montrent (spanish (david))

Answer 1

Une tâche à base itération comme cela est le mieux adapté à son Common Lisp extrêmement puissant loop macro. Vous pouvez lire tous les détails de cette macro dans the GigaMonkeys book, mais nous allons simplement passer en revue les parties dont vous avez besoin pour ce problème ici. Commençons par la définition de la fonction.

(defun lenguages (names) 
    ...) 

nous voulons Dans ce, à itérer sur la liste fournie. Nous voulons également collecter des clés, donc une table de hachage serait utile. Les tables de hachage (appelées cartes ou dicts dans de nombreuses autres langues) associent les clés aux valeurs de manière efficace.

(loop with hash = (make-hash-table) 
     for entry in names 
     for name = (car entry) 
     do ... 
     finally ...) 

La macro loop est très puissant et a un langage qui lui est propre. La clause with déclare une variable locale, dans ce cas une table de hachage. Le premier for définit une variable d'itération. La boucle fonctionnera avec entry lié à chaque entrée de names et s'arrêtera lorsqu'il n'y aura plus d'entrées. La troisième ligne est une autre variable locale, mais contrairement à with, une variable for est rebondie à chaque fois, donc à chaque itération name sera le premier élément de entry. Le bloc do contient du code Lisp arbitraire qui sera exécuté à chaque itération et finally contient un bloc de code Lisp à exécuter à la fin de la boucle.

À l'intérieur du bloc do, nous souhaitons ajouter le nom de la personne à l'entrée de la table de hachage pour chaque langue connue. Nous avons donc besoin d'un autre loop pour parcourir les langues connues.

(loop for lang in (cdr entry) 
     do (push name (gethash lang hash))) 

Cette boucle va à l'intérieur du bloc do de l'une extérieure. Pour chaque langue de la liste des langues connues de la personne, nous souhaitons ajouter le nom de cette personne à la valeur de hachage de cette langue. Normalement, nous devrions considérer le cas dans lequel la clé de hachage n'existe pas, mais heureusement pour nous Common Lisp par défaut à nil si la clé de hachage n'existe pas, et en ajoutant un élément à nil crée une liste d'un élément, ce qui est juste ce que nous voulons.

Maintenant, lorsque cette boucle est terminée, la table de hachage contiendra toutes les langues et clés et listes de personnes qui les connaissent comme valeurs. Ce sont les données que vous voulez, mais ce n'est pas dans le format que vous voulez.En fait, si nous mettons cela dans notre finally bloc

(return hash) 

Nous obtiendrions une sortie semi-utile * qui nous dit que nous sommes sur la bonne voie. Au lieu de cela, faisons une autre boucle pour convertir cette table de hachage à la liste que vous voulez qu'elle soit. Voici ce que nous voulons dans le bloc finally maintenant.

(return (loop for key being the hash-keys of hash using (hash-value value) 
       collect (list key value))) 

Il utilise la syntaxe being relativement obscure pour la loop macro, ce qui permet l'itération facile sur les tables de hachage. Vous devriez lire ceci: pour chaque paire clé-valeur, collecter une liste contenant la clé suivie de la valeur dans une liste, puis retourner la liste accumulée. C'est encore une des caractéristiques intéressantes des macros loop: il essaie de fournir des primitives pour des cas d'utilisation courants tels que l'accumulation de valeurs dans une liste. Et il est utile dans les cas comme celui-ci.

Voici le bloc de code complet.

(defun lenguages (names) 
    (loop with hash = (make-hash-table) 
     for entry in names 
     for name = (car entry) 
     do (loop for lang in (cdr entry) 
       do (push name (gethash lang hash))) 
     finally (return (loop for key being the hash-keys of hash using (hash-value value) 
           collect (list key value))))) 

Ce lien que je fourni plus tôt est le livre de GigaMonkeys sur Common Lisp, qui est available online for free. Je vous encourage fortement à le lire, car c'est une référence incroyable pour tout ce qui est commun. Surtout si vous débutez, ce livre peut vraiment vous mettre dans la bonne direction.

---

_{* Votre format de sortie peut varier. L'implémentation choisit comment générer les structures.}

Answer 2

L'autre réponse est correcte: voici une version qui n'utilise pas loop ou des tables de hachage intermédiaires, mais qui construit directement la liste d'associations requise. Il vaut la peine de comparer son efficacité avec celle de la table de hachage: il fait beaucoup plus de recherche dans les listes, mais en pratique, pour de petites quantités de données, ces choses sont souvent plus rapides (les hashtables ont un overhead non trivial dans de nombreuses implémentations). utilisera toujours moins de stockage car il ne construit aucune structure qu'il ne retourne pas.

Notez que:

• cette obtenir des résultats dans un ordre différent en général (il n'a pas de dépendance à l'ordre de hachage);
• (languages '((david german german))) est est et non ((german (david david))) - il paie un certain coût de performance (qui pourrait être amélioré pour les grandes données en utilisant plus de hashtables) pour ce faire.

Alors, voici:

(defun languages (people) 
    (let ((langs '()))     ;the map we are building 
    (dolist (pl people langs) 
     (destructuring-bind (person . person-languages) pl 
     (dolist (lang person-languages) 
      (let ((entry (assoc lang langs))) 
      (if (not (null entry)) 
       ;; there's an entry for lang: add the person to it 
       (pushnew person (second entry)) 
       ;; there is no entry, create one with person in it 
       (setf langs `((,lang (,person)) ,@langs))))))))) 

---

(Notez également que la version basée loop pourrait utiliser destructuration de loop, ce qui pourrait être un peu plus clair.)