Prolog - jak dodać element do listy?

Question

Jeśli mam listę w Prologu, taką jak X = [1, 2, 3, 4], w jaki sposób dodać element 5 na końcu listy, aby X = [1, 2, 3, 4, 5 ]?

Funkcja dołączająca potrzebuje dwa wykazy, czyli dołączanie (A, B, C), aby A oraz B dołączona do listy C

może zrobić to z wykazu czasowego Y = [1, 2, 3, 4] i Z = [5], aby następnie dołączyć (Y, Z, X), ale nie lubię mieć listy tymczasowej.

Stosuje się tutaj zwykłe zrzeczenia się - to nie jest praca domowa i dopiero się uczę Prologu.

Answer 1

Zmienne w Prolog mogą być przypisane tylko raz. Jak tylko X ma wartość [1,2,3,4], nigdy nie może mieć innej wartości. Zmienna tymczasowa i dodatek/3, jak wspomniałeś, to sposób na zrobienie tego.

Powiedziawszy to, możesz zrobić jedną sztuczkę, która prawdopodobnie nie jest zalecana. Jeśli X = [1,2,3,4, Y], możesz zrobić Y = 5, a X ma teraz żądaną wartość. Wierzę, że ta technika nazywa się różnicą.

Answer 2

Martwisz się złym końcem problemu. Współdzielenie struktury może się zdarzyć tylko przez umieszczenie elementu na początku listy. Ta metoda ma pożądaną charakterystykę wydajności. Ze względu na sposób definiowania list, po dołączeniu dwóch list zostanie skopiowana cała pierwsza lista. W tym przypadku będzie to cała lista. Śmieci generowane przez listę przedmiotów z jednego przedmiotu będą oczywiście znacznie mniejsze.

Jeśli naprawdę musisz dołączyć, rozważ utworzenie listy wstecz, a następnie cofnij ją raz na końcu, co jest znacznie tańsze, lub użyj list różnicowych, które umożliwiają efektywne dołączanie do końca.

Answer 3

Jak wskazali inni, utkniesz z problemem z wydajnością.
Jednak jako ćwiczenie postanowiłem spróbować stworzyć predykat, który może dopisać element na końcu listy, bez używania 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). 

radziłbym że chcesz po prostu użyć funkcji append jako wbudowaną funkcją jest prawdopodobnie szybciej niż cokolwiek ręcznie spreparowane.

Answer 4

Jednym z deklaratywnych rozwiązań jest użycie listy różnic (jak sugerował Daniel w swojej odpowiedzi). Na liście różnicowej jej nazwa jest zwykle przedstawiana jako różnica między dwiema listami: listą i ogonem. Na przykład pusta lista może być reprezentowana jako T-T. Lista z elementami 1, 2 i 3 może być reprezentowana jako [1,2,3| T]-T (zauważ, że (-)/2 jest standardowym wbudowanym operatorem infiksów). Zaletą tej reprezentacji jest to, że można dodać element do listy w stałym czasie przy użyciu pojedynczego definicję fakt append/3 orzecznika:

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

Przykład użycia:

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

Jeśli to konieczne, nie jest trudne do przekonwertowania między "normalną" listą a listą różnic. Zostawiam to jako ćwiczenie dla ciebie.

Answer 5

Nie można modyfikować list w Prologu, ale można utworzyć listę o długości nieokreślonym:

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

Następnie można wstawić element używając nth0/3 w SWI-Prolog:

:- initialization(main). 

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

Po wstawieniu tego elementu, A = [1,2,3,4,5|_].

Można również zdefiniować funkcję, która Dołącza element na końcu listy w miejscu, a następnie używać go tak:

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

w tym przykładzie, A = [1,2,3,4,4|_] Po tych dwóch elementów są dołączone.

Answer 6

Od kiedy Prolog ma dodatek, który akceptuje tylko listy, dlaczego nie użyjemy wstawić nasz element na jednej z list. tj.

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