Если у меня есть список в Прологе, такой как X = [1, 2, 3, 4], как мне добавить элемент 5 в конец списка, чтобы X = [1, 2, 3, 4, 5]?
Функция добавления нуждается в двух списках, т.е. append (A, B, C), чтобы объединить A и B в список C.
Я могу сделать это с помощью временного списка Y = [1, 2, 3, 4] и Z = [5], чтобы затем выполнить добавление (Y, Z, X), но мне не нравится иметь временный список.
Здесь действуют обычные оговорки - это не домашнее задание, и я только изучаю Пролог.
Переменные в Прологе могут быть присвоены только один раз. Как только X имеет значение [1,2,3,4], он никогда не сможет иметь другое значение. Временная переменная и добавление / 3, как вы упомянули, - это способ сделать это.
Сказав это, вы можете сделать один трюк, который, вероятно, не рекомендуется. Если X = [1,2,3,4, Y], тогда вы можете сделать Y = 5, и теперь X имеет желаемое значение. Я считаю, что этот метод называется списком различий.
X = [1,2,3,4 | Y], а затем Y = [5 | Z] это техника списка различий: добавление 5 в конце X...Y дает нам удлиненный X...Z. первый X...Y является все еще действующим, более коротким списком различий, по-прежнему представляющим тот же префикс 1,2,3,4, что и до расширения. Список различий легко понять как открытые списки или префиксы. Кроме того, расширение списка различий таким образом является операцией O (1).
- person Will Ness; 06.06.2018
Как отмечали другие, вы застрянете с проблемой производительности.
Но в качестве упражнения я решил попробовать создать предикат, который мог бы добавлять элемент в конец списка без использования 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).
Я бы посоветовал вам просто использовать функцию append, поскольку как встроенная функция она, вероятно, будет быстрее, чем что-либо созданное вручную.
add_tail(X,[L1],[L2]) и add_tail(X,[Y|L1],[Z|L2])?
- person tamaramaria; 18.10.2016
Одно декларативное решение - использовать список различий (как предложил Дэниел в своем ответе). Список различий получил свое название из-за того, что обычно он представлен как различие между двумя списками: списком и его хвостом. Например, пустой список можно представить как T-T. Список с элементами 1, 2 и 3 может быть представлен как [1,2,3| T]-T (обратите внимание, что (-)/2 - стандартный встроенный инфиксный оператор). Преимущество этого представления в том, что вы можете добавить элемент в список за постоянное время, используя одно определение факта предиката append/3:
append(L1-T1, T1-T2, L1-T2).
Пример использования:
?- append([1,2,3,4| T1]-T1, [5| T2]-T2, Result).
T1 = [5|T2],
Result = [1, 2, 3, 4, 5|T2]-T2.
При необходимости нетрудно конвертировать между "нормальным" списком и списком различий. Я оставляю это вам в качестве упражнения.
Вы не можете изменять списки в Prolog, но вы можете создать список с неопределенной длиной:
main :-
A = [1,2,3,4|_].
Затем вы можете вставить элемент, используя nth0/3 в SWI- Пролог:
:- initialization(main).
main :-
A = [1,2,3,4|_],
nth0(4,A,5),
writeln(A).
После вставки этого элемента A = [1,2,3,4,5|_].
Вы также можете определить функцию, которая добавляет элемент в конец списка на месте, а затем использовать ее следующим образом:
:- 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).
В этом примере A = [1,2,3,4,4|_] после добавления этих двух элементов.
Поскольку в Прологе есть добавление, которое принимает только списки, почему бы нам не использовать его для вставки нашего элемента в один из списков. т.е.
% 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).
Вы беспокоитесь о неправильном конце проблемы. Разделение структуры может произойти только путем включения элемента в начало списка. Этот метод обладает желаемыми характеристиками производительности. Из-за способа определения списков, когда вы добавляете два списка, весь первый список будет скопирован. В данном случае это будет весь список. Мусор, создаваемый списком из одного элемента, очевидно, будет намного меньше этого.
Если вам действительно нужно добавить, подумайте о том, чтобы построить список в обратном порядке, а затем перевернуть его один раз в конце, что намного дешевле, или используйте списки различий, которые обеспечивают эффективное добавление в конец.
