ti-enxame.com

Como você anexa um elemento a uma lista no Prolog?

Se eu tiver uma lista no Prolog como X = [1, 2, 3, 4], como adiciono o elemento 5 ao final da lista para ter X = [1, 2, 3, 4, 5]?

A função append precisa de duas listas, isto é, append (A, B, C) para obter A e B concatenadas na lista C.

Eu posso fazer isso com uma lista temporária Y = [1, 2, 3, 4] e Z = [5], para então fazer um acréscimo (Y, Z, X), mas não gosto de ter uma lista temporária.

As isenções de responsabilidade usuais se aplicam aqui - isso não é tarefa de casa e estou apenas aprendendo o Prolog.

15
No One in Particular

Variáveis ​​no Prolog podem ser atribuídas apenas uma vez. Assim que X tiver o valor [1,2,3,4], ele nunca poderá ter outro valor. Uma variável temporária e append/3, como você mencionou, é a maneira de fazê-lo.

Dito isto, você pode executar um truque que provavelmente não é recomendado. Se X = [1,2,3,4, Y], você pode fazer Y = 5 e X agora tem o valor desejado. Eu acredito que essa técnica é chamada de lista de diferenças.

6
mndrix

Como os outros apontaram, você ficará preso ao problema de desempenho.
Mas, como exercício, decidi tentar criar um predicado que pudesse acrescentar um elemento ao final de uma lista, sem usar 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).

Eu recomendaria que você simplesmente usasse a função append, como uma função interna provavelmente será mais rápida do que qualquer coisa criada manualmente.

7
S.L. Barth

Uma solução declarativa é usar uma lista de diferenças (como Daniel sugeriu em sua resposta). Uma lista de diferenças recebe seu nome geralmente representada como uma diferença entre duas listas: uma lista e sua cauda. Por exemplo, uma lista vazia pode ser representada como T-T. Uma lista com os elementos 1, 2 e 3 pode ser representada como [1,2,3| T]-T (Observe que (-)/2 é um operador de infixo interno padrão). A vantagem dessa representação é que você pode anexar um elemento a uma lista em tempo constante usando uma única definição de fato do append/3 predicado:

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

Um exemplo de uso:

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

Se necessário, não é difícil converter entre uma lista "normal" e uma lista de diferenças. Deixo isso como um exercício para você.

3
Paulo Moura

Você está preocupado com o lado errado do problema. O compartilhamento de estrutura só pode acontecer inserindo um elemento no início da lista. Esse método tem as características de desempenho que você deseja. Devido à maneira como as listas são definidas, quando você anexa duas listas, a primeira lista inteira será copiada. Nesse caso, essa será a lista completa. O lixo gerado por uma lista de um item obviamente será muito menor que isso.

Se você realmente precisa anexar, considere construir a lista ao contrário e depois revertê-la uma vez no final, o que é muito mais barato, ou use listas de diferenças, que permitem anexar com eficiência ao final.

2
Daniel Lyons

Você não pode modificar listas no Prolog, mas pode criar uma lista com um comprimento não especificado:

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

Em seguida, você pode inserir um elemento usando nth0/3 no SWI-Prolog:

:- initialization(main).

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

Depois que esse elemento é inserido, A = [1,2,3,4,5|_].

Você também pode definir uma função que anexa um item ao final de uma lista no local e usá-lo assim:

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

Neste exemplo, A = [1,2,3,4,4|_] depois que esses dois itens forem anexados.

2
Anderson Green

Como o Prolog anexa o que aceita apenas listas, por que não o usamos para inserir nosso elemento em uma das listas. isto é.

% 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).
1
Imam Bux