Prolog - Wie hängt man ein Element an eine Liste an?

Question

Wenn ich eine Liste in Prolog wie X = [1, 2, 3, 4] habe, wie füge ich das Element 5 an das Ende der Liste, um X = [1, 2, 3, 4, 5 ]?

APPEND Funktion benötigt zwei Listen, nämlich append (A, B, C) verketteten A und B zu erhalten, auf die Liste C.

I dies mit einer temporären Liste tun kann, Y = [1, 2, 3, 4] und Z = [5], um dann einen Anhang (Y, Z, X) zu machen, aber ich mag es nicht, eine temporäre Liste zu haben.

Die üblichen Disclaimer gelten hier - das sind keine Hausaufgaben und ich lerne nur Prolog.

Answer 1

Variablen in Prolog können nur einmal vergeben werden. Sobald X den Wert [1,2,3,4] hat, kann es niemals einen anderen Wert haben. Eine temporäre Variable und append/3, wie du erwähnt hast, ist der Weg, dies zu tun.

Having said that, können Sie einen Trick, der wahrscheinlich nicht empfohlen wird. Wenn X = [1,2,3,4, Y], dann können Sie Y = 5 und X hat jetzt den gewünschten Wert. Ich glaube, dass diese Technik eine Differenzliste genannt wird.

Answer 2

Sie machen sich Sorgen um das falsche Ende des Problems. Struktur-Sharing kann nur geschehen, indem ein Element am Anfang der Liste eingefügt wird. Diese Methode hat die von Ihnen gewünschten Leistungsmerkmale. Aufgrund der Art, wie Listen definiert sind, wird beim Anhängen von zwei Listen die gesamte erste Liste kopiert. In diesem Fall wird das die ganze Liste sein. Der Müll, der durch eine Ein-Punkt-Liste erzeugt wird, wird offensichtlich viel kleiner sein.

Wenn Sie wirklich anhängen müssen, ziehen Sie in Betracht, die Liste rückwärts zu erstellen und dann am Ende einmal umzukehren, was viel billiger ist, oder verwenden Sie Differenzlisten, die ein effizientes Anhängen an das Ende ermöglichen.

Answer 3

Wie die anderen darauf hingewiesen haben, werden Sie mit dem Leistungsproblem festhängen.
Aber gerade als eine Übung habe ich mich entschieden, ein Prädikat zu erstellen, das ein Element an das Ende einer Liste anhängen könnte, ohne append zu verwenden.

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

Ich würde empfehlen, dass man einfach die append Funktion verwenden würde, als integrierte Funktion ist es wahrscheinlich, etwas schneller zu sein als von Hand gefertigt.

Answer 4

Eine deklarative Lösung besteht darin, eine Differenzliste zu verwenden (wie Daniel in seiner Antwort vorgeschlagen hat). Eine Differenzenliste erhält ihren Namen dadurch, dass sie in der Regel als ein Unterschied zwischen zwei Listen dargestellt wird: einer Liste und ihrem Ende. Zum Beispiel kann eine leere Liste als T-T dargestellt werden. Eine Liste mit den Elementen 1, 2 und 3 kann als [1,2,3| T]-T dargestellt werden (beachten Sie, dass (-)/2 der standardmäßige integrierte Infix-Operator ist). Der Vorteil dieser Darstellung ist, dass Sie ein Element einer Liste in konstanter Zeit unter Verwendung einer einzigen Tatsache Definition des append/3 Prädikat anfügen können:

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

Ein Anwendungsbeispiel:

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

Falls erforderlich, Es ist nicht schwer, zwischen einer "normalen" Liste und einer Differenzliste zu konvertieren. Das überlasse ich Ihnen als Übung.

Answer 5

Sie können keine Listen in Prolog ändern, aber Sie können eine Liste mit einer unbestimmten Länge erstellen:

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

Dann können Sie ein Element mit nth0/3 in SWI-Prolog einfügen:

:- initialization(main). 

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

Nachdem dieses Element eingefügt wurde, A = [1,2,3,4,5|_].

Sie können auch eine Funktion definieren, die ein Element am Ende einer Liste in-Place anhängt, und es dann wie folgt verwenden:

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

In diesem Beispiel A = [1,2,3,4,4|_] nach diesen beiden Positionen angehängt werden.

Answer 6

Da Prolog append hat, das nur Listen akzeptiert, verwenden wir unser Element nicht in eine der Listen. d.h.

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