Prolog - comment ajouter un élément à une liste?

Question

Si j'ai une liste en Prolog telle que X = [1, 2, 3, 4], comment ajouter l'élément 5 à la fin de la liste pour avoir X = [1, 2, 3, 4, 5 ]?

La fonction d'ajout a besoin de deux listes, à savoir append (A, B, C) pour obtenir A et B concaténé à la liste C.

je peux le faire avec une liste temporaire Y = [1, 2, 3, 4] et Z = [5], pour ensuite faire un append (Y, Z, X), mais je n'aime pas avoir une liste temporaire.

Les clauses de non-responsabilité habituelles s'appliquent ici - ce n'est pas un devoir et j'apprends simplement Prolog.

Answer 1

Les variables dans Prolog ne peuvent être affectées qu'une seule fois. Dès que X a la valeur [1,2,3,4], il ne peut jamais avoir une autre valeur. Une variable temporaire et append/3, comme vous l'avez mentionné, est la façon de le faire.

Cela dit, vous pouvez faire un tour qui n'est probablement pas recommandé. Si X = [1,2,3,4, Y] alors vous pouvez faire Y = 5 et X a maintenant la valeur que vous voulez. Je crois que cette technique s'appelle une liste de différence.

Answer 2

Vous vous inquiétez de la mauvaise fin du problème. Le partage de structure ne peut se faire qu'en disposant un élément au début de la liste. Cette méthode a les caractéristiques de performance que vous voulez. En raison de la façon dont les listes sont définies, lorsque vous ajoutez deux listes, la première liste entière sera copiée. Dans ce cas, ça va être toute la liste. Les déchets générés par une liste à un seul article vont évidemment être beaucoup plus petits que cela.

Si vous devez vraiment ajouter, pensez à reconstruire la liste à l'envers et à l'inverser une fois à la fin, ce qui est beaucoup moins cher, ou utilisez des listes de différences, qui permettent d'ajouter efficacement jusqu'à la fin.

Answer 3

Comme d'autres l'ont fait remarquer, vous allez être bloqué avec le problème de performance.
Mais juste comme un exercice, j'ai décidé d'essayer de créer un prédicat qui pourrait ajouter un élément à la fin d'une liste, sans utiliser append.

% add_tail(+List,+Element,-List) 
% Add the given element to the end of the list, without using the "append" predicate. 
add_tail([],X,[X]). 
add_tail([H|T],X,[H|L]):-add_tail(T,X,L). 

Je vous conseille que vous souhaitez simplement utiliser la fonction append, en fonction intégrée, il est susceptible d'être plus rapide que tout conçu manuellement.

Answer 4

Une solution déclarative consiste à utiliser une liste de différences (comme Daniel l'a suggéré dans sa réponse). Une liste de différences obtient son nom d'être généralement représenté comme une différence entre deux listes: une liste et sa queue. Par exemple, une liste vide peut être représentée par T-T. Une liste avec les éléments 1, 2 et 3 peut être représentée par [1,2,3| T]-T (notez que (-)/2 est un opérateur infixe intégré standard). L'avantage de cette représentation est que vous pouvez ajouter un élément à une liste constante de temps en utilisant une définition unique de fait du prédicat append/3:

append(L1-T1, T1-T2, L1-T2). 

Un exemple d'utilisation:

?- append([1,2,3,4| T1]-T1, [5| T2]-T2, Result). 
T1 = [5|T2], 
Result = [1, 2, 3, 4, 5|T2]-T2. 

Si nécessaire, n'est pas difficile à convertir entre une liste "normale" et une liste de différences. Je laisse cela comme un exercice pour vous.

Answer 5

Vous ne pouvez pas modifier les listes en Prolog, mais vous pouvez créer une liste avec une durée indéterminée:

main :- 
    A = [1,2,3,4|_]. 

Ensuite, vous pouvez insérer un élément en utilisant nth0/3 dans SWI-Prolog:

:- initialization(main). 

main :- 
    A = [1,2,3,4|_], 
    nth0(4,A,5), 
    writeln(A). 

Une fois cet élément inséré, A = [1,2,3,4,5|_].

Vous pouvez également définir une fonction qui ajoute un élément à la fin d'une liste en place, puis l'utiliser comme ceci:

:- initialization(main). 

append_to_list(List,Item) :- 
    List = [Start|[To_add|Rest]], 
    nonvar(Start), 
    (var(To_add),To_add=Item;append_to_list([To_add|Rest],Item)). 

main :- 
    A = [1,2,3|_], 
    append_to_list(A,4), 
    append_to_list(A,4), 
    writeln(A). 

Dans cet exemple, A = [1,2,3,4,4|_] après ces deux éléments sont annexés.

Answer 6

Étant donné que Prolog a append qui n'accepte que des listes, pourquoi n'utilisons-nous pas insert notre élément dans l'une des listes. c'est-à-dire

% E = element, L = list, R = result 
% e.g. add_elem_in_list ([1,2,3,4], 5, R). 
add_elem_in_list(L, E, R) :- append(L, [E], R).