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

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

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

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

Answer 3

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

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

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

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

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

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

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 4

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

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 способ решения данной проблемы, а не предполагать, что он должен решаться с использованием шаблона, более подходящего для другого типа. языка.