Двусвязный список в Прологе

Question

Я изучал Пролог в свое свободное время от 8 месяцев до года, и теперь я перехожу к реализации некоторых классических структур данных и алгоритмов.

Я заинтересован в достижении вдвойнесвязанный список в Прологе, но довольно озадачен относительно того, как продолжить.Я был привлечен к Прологу, потому что меня интересует «логическая чистота».

Кажется, что я настолько приспособлен к объектно-ориентированной парадигме, что без простого я просто не могу без нее обойтись!

Для справки по двусвязному списку я имею в виду нечто похожее на то, что описано в этой ссылке:

Двусвязный список

Answer 1

Что делает его двусвязным списком, так это то, что он имеет две ссылки, а не одну, ссылку на предыдущий и следующий элемент в списке.Таким образом, мы могли бы создать структуру node(Value, Previous, Next) и составить список вручную следующим образом: A = node(1, nil, B), B = node(2, A, nil)..Мы могли бы сделать более длинные списки аналогичным способом, просто создав больше промежуточных переменных.

Преобразование этого обратно в «обычный» список будет выглядеть примерно так:

dl2list(node(X, _, nil), [X]).
dl2list(node(A, _, node(X,Y,Z)), [A|Rest]) :- dl2list(node(X,Y,Z), Rest).

Это не имеет особого примененияиз «предыдущего» указателя, но вы можете видеть, что он работает:

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   dl2list(A, L).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [1, 2, 3, 4] .

Мы также можем строить в обратном направлении, начиная с конца:

dl2listrev(node(X, nil, _), [X]).
dl2listrev(node(A, node(X,Y,Z), _), [A|Rest]) :- dl2listrev(node(X,Y,Z), Rest).

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   dl2listrev(D, L).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [4, 3, 2, 1] 

Для создания двусвязного спискаИз списка вам нужно что-то немного более сильное, чем любой из этих:

l2dl(L, DL) :- l2dl(L, DL, nil).

l2dl([X], node(X, Prev, nil), Prev).
l2dl([X,Y|Xs], node(X, Prev, Next), Prev) :- 
    l2dl([Y|Xs], Next, node(X, Prev, Next)).

Это вы можете увидеть, работая в обоих направлениях здесь:

?- l2dl([1,2,3,4], X), dl2list(X, L).
X = node(1, nil, node(2, _S1, node(3, _S2, _S3))), % where
    _S1 = node(1, nil, node(2, _S1, node(3, _S2, _S3))),
    _S2 = node(2, _S1, node(3, _S2, _S3)),
    _S3 = node(4, node(3, _S2, _S3), nil),
L = [1, 2, 3, 4] 

и здесь:

?- A = node(1, nil, B), 
   B = node(2, A, C), 
   C = node(3, B, D), 
   D = node(4, C, nil), 
   l2dl(L, A).
A = node(1, nil, _S1), % where
    _S1 = node(2, node(1, nil, _S1), _S2),
    _S2 = node(3, _S1, node(4, _S2, nil)),
B = node(2, node(1, nil, _S1), _S2),
C = node(3, _S1, node(4, _S2, nil)),
D = node(4, _S2, nil),
L = [1, 2, 3, 4] 

Answer 2

Это вопрос, который продолжает появляться.Вам действительно нужно объяснить, что вы пытаетесь сделать с этим двусвязным списком.Я очень соблазняюсь подать это еще раз в мою коллекцию восхитительных XY проблем экспонатов.

популярное мнение по теме - это "самый простой способ получитьк реальной проблеме обычно задают вопрос «Почему пять раз».

Итак: Зачем вам нужен двусвязный список?Вы реализуете очередь?Сортированный список, который вы хотите пройти в обе стороны?Что-то еще?

И чтобы сделать это более реальным ответом:

Если вы используете обычный список, вы можете изменить его, когда вам понадобится другой конец.

Если вам нужна очередь, которую можно протолкнуть с обоих концов и вытолкнуть с одного конца, вы можете использовать очередь Пролога:

queue_empty(q(0, Q, Q)).
queue_back(q(N, Q, [X|Q0]), X, q(s(N), Q, Q0)).
queue_front(q(N, Q, Q0), X, q(s(N), [X|Q], Q0)).

Это действительно зависит от того, зачем вам нужен двусвязный список?Каков ваш вариант использования?

Answer 3

Как обсуждалось в комментариях к исходному вопросу, как и в SQL, вы можете утверждать факты в Прологе, которые можно использовать как связанный список:

head_node(Id).
node(Id, Data, LeftId, RightId).

Вы можете обозначить атом nil какваше нулевое значение.

В качестве очень простого примера:

head_node(a).

node(a, 123, nil, c).
node(b, 214, c, nil).
node(c, 312, a, b).

Затем вы можете написать предикаты для обработки этих данных:

remove_node(NodeId) :-
    node(NodeId, _, LeftId, RightId),
    ...

Остальные ...может быть написано с помощью retract, assertz и т. д. Однако, как отмечает Гай Кодер в своих комментариях, этому не хватает логической чистоты, что, похоже, является первоначальной задачей.Структура данных громоздка в использовании, и, как я уже упоминал в комментариях, лучше найти более подходящий Prolog-esque способ решения данной проблемы, а не предполагать, что он должен решаться с использованием шаблона, более подходящего для другого типа.языка.

Answer 4

Одной из возможных материализаций двойного связного списка в Прологе является использование молнии .Если вы не знакомы с этой концепцией, см., Например,

https://en.wikipedia.org/wiki/Zipper_(data_structure)

. Застежка-молния позволяет перемещаться по списку вперед и назад, обеспечивая доступ к текущему элементу.Таким образом, он обеспечивает функциональность, общую для списков с двойной связью.Logtalk (который вы можете запустить с большинством компиляторов Prolog) включает в себя поддержку библиотеки для застежек-молний.Протокол молнии можно просмотреть по адресу:

https://logtalk.org/library/zipperp_0.html

Этот протокол реализован для списков объектом zlist.Вы можете просмотреть его код по адресу:

https://github.com/LogtalkDotOrg/logtalk3/blob/master/library/zlist.lgt

Обратите внимание, что большинство предикатов чисто с некоторыми из них, определяемыми фактами.Также есть пример использования по адресу:

https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/slides