Prolog: come si aggiunge un elemento a un elenco in posizione?

Question

Se ho un elenco in Prolog come X = [1, 2, 3, 4], come faccio ad aggiungere l'elemento 5 alla fine dell'elenco per avere X = [1, 2, 3, 4, 5 ]?

La funzione di accodamento bisogno di due liste, cioè aggiungono (A, B, C) per ottenere A e B concatenato all'elenco C.

posso fare questo con una lista temporanea Y = [1, 2, 3, 4] e Z = [5], per fare poi un'appendice (Y, Z, X), ma non mi piace avere una lista temporanea.

Qui si applicano le normali dichiarazioni di non responsabilità - questo non è compito a casa e sto solo imparando Prolog.

Answer 1

Le variabili in Prolog possono essere assegnate una sola volta. Non appena X ha il valore [1,2,3,4] non può mai avere un altro valore. Una variabile temporanea e append/3, come hai detto tu, è il modo per farlo.

Detto questo, puoi fare un trucco che probabilmente non è raccomandato. Se X = [1,2,3,4, Y] allora puoi fare Y = 5 e X ora ha il valore che vuoi. Credo che questa tecnica sia chiamata una lista di differenze.

Answer 2

Ti stai preoccupando della fine sbagliata del problema. La condivisione della struttura può avvenire solo se si aggiunge un elemento all'inizio della lista. Questo metodo ha le caratteristiche di prestazione che desideri. A causa del modo in cui sono definite le liste, quando si aggiungono due elenchi verrà copiato l'intero primo elenco. In questo caso, questa sarà l'intera lista. La spazzatura generata da una lista di un solo oggetto ovviamente sarà molto più piccola di quella.

Se davvero si deve aggiungere, considerare la possibilità di creare un elenco a ritroso e quindi di invertirlo una volta alla fine, che è molto più economico, o utilizzare liste di differenze, che consentono di aggiungere in modo efficiente fino alla fine.

Answer 3

Come gli altri hanno sottolineato, rimarrai bloccato con il problema delle prestazioni.
Ma proprio come esercizio ho deciso di provare e creare un predicato che potrebbe aggiungere un elemento alla fine di un elenco, senza utilizzare 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). 

vorrei consigli che ti sentiresti sufficiente utilizzare la funzione append, come una funzione built-in, è probabile che sia più veloce di qualsiasi artigianale manualmente.

Answer 4

Una soluzione dichiarativa consiste nell'utilizzare un elenco di differenze (come suggerito da Daniel nella sua risposta). Un elenco di differenze prende il nome dall'essere solitamente rappresentato come una differenza tra due liste: una lista e la sua coda. Ad esempio, una lista vuota può essere rappresentata come T-T. Un elenco con gli elementi 1, 2 e 3 può essere rappresentato come [1,2,3| T]-T (notare che (-)/2 è l'operatore infisso incorporato standard). Il vantaggio di questa rappresentazione è che è possibile aggiungere un elemento a un elenco in tempo costante utilizzando una definizione unica realtà del append/3 predicato:

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

Un esempio di utilizzo:

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

Se necessario, non è difficile convertire tra un elenco "normale" e un elenco di differenze. Lo lascio come esercizio per te.

Answer 5

Non è possibile modificare gli elenchi in Prolog, ma è possibile creare una lista con una lunghezza non specificata:

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

Quindi, è possibile inserire un elemento utilizzando nth0/3 in SWI-Prolog:

:- initialization(main). 

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

Dopo aver inserito questo elemento, A = [1,2,3,4,5|_].

È possibile anche definire una funzione che aggiunge un elemento alla fine di un elenco sul posto, e quindi usare in questo modo:

:- 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 questo esempio, A = [1,2,3,4,4|_] dopo questi due elementi vengono aggiunti.

Answer 6

Dal momento che Prolog ha aggiunto che accetta solo elenchi, perché non usiamo inserire il nostro elemento in uno degli elenchi. Ad esempio

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