Я понимаю, что некоторые Prologs поддерживают словарно-подобные ассоциативные структуры данных из коробки. Для реализации, которые это делают, поддерживают ли они некоторое понятие частичной унификации с другой структурой, которая фактически не содержит всех ключей?
Это вернет единственный результат, где q связано с 1.
Ответ 1
Некоторые системы Prolog, такие как Eclipse, имеют запись записи. Это можно использовать
когда вы заранее знаете возможные ключи вашей карты. Но это необходимо
объявление типа. Запись записи также содержится в Prolog decendant
такие языки, как Эрланг.
Идея очень проста. Вы сначала объявляете
тип записи (какой-то синтаксис, изобретенный здесь):
:- rectype T{K1,...,Kn}.
Теперь вы можете использовать внутри своей программы Prolog
записи, просто напишите (опять-таки какой-то синтаксис, изобретенный здесь):
... T{F1 = V1, .., Fn = Vm} ...
При компиляции тип записи будет преобразован в состав
и тогда их можно легко использовать при нормальном объединении. Преобразование
переупорядочивает пары значений ключа в соответствии с типом записи
декларации, затем отбрасывает ключи и использует только позиции.
Неиспользованные позиции заменяются анонимными переменными или
по умолчанию, если объявление типа записи также
охватывает это.
... T(W1, ..., Wn) ...
Ваш пример будет работать следующим образом:
:- rectype myrec{foo, bar}
?- myrec{foo=1,bar=2} = myrec{foo=q}
Последний запрос будет внутренне выполнен как:
?- myrec(1,2) = myrec(q,_).
Подробнее о том, как это работает Eclipse, см. здесь:
http://www.eclipseclp.org/doc/bips/kernel/syntax/struct-1.html
Для динамических карт, где набор ключей не является статическим, вы можете реализовать
динамические структуры данных, как и другие сообщения о SWI-Prolog AVL
деревья показывают. Или попросите систему Prolog описать конкретную
структура данных. Реализуйте их с помощью FFI (интерфейс внешних функций)
или доступ к ним, которые уже включены в систему Prolog.
Например, Eclipse связывает пару, см. Раздел "Описание"
в следующей статье:
http://www.eclipseclp.org/doc/bips/kernel/record/index.html
Bye
Ответ 2
Как правило, в Prolog используется стандартный выбор основных типов данных в Prolog: путем добавления библиотек и использования интерфейсов. SWI-Prolog, например, поставляется с библиотекой assoc, которая реализует основанную на AVL ассоциацию структура данных. (В стороне сбалансированные деревья чаще встречаются в функциональном и логическом программировании, чем хеш-таблицы, потому что легче создавать "постоянные" структуры данных на деревьях, чем хеш-таблицы, - стойкие в смысле использования внутренней структуры FP.)
Использование этой библиотеки выглядит примерно так:
?- [library(assoc)].
% library(assoc) compiled into assoc 0.00 sec, 97 clauses
true.
?- empty_assoc(Assoc).
Assoc = t.
?- empty_assoc(Assoc), get_assoc(test, Assoc, V).
false.
?- empty_assoc(Assoc), put_assoc(test, Assoc, foo, Assoc2).
Assoc = t,
Assoc2 = t(test, foo, -, t, t).
?- empty_assoc(Assoc),
put_assoc(test, Assoc, foo, Assoc2),
get_assoc(test, Assoc2, Value).
Assoc = t,
Assoc2 = t(test, foo, -, t, t),
Value = foo.
Как только у вас есть что-то, что дает вам такой интерфейс, вы можете определить все виды логических отношений поверх него. Когда у вас есть логические отношения, система нормального унификации Prolog позаботится об остальном - никакой специальной поддержки для того или иного типа данных не требуется. Основываясь на ваших требованиях, я думаю, что вы хотите, как отношение подмножества, за исключением проверки того, что все одна ассоциация находится в другой, и все они имеют одинаковое значение. Я предполагаю, что это будет выглядеть примерно так:
association_subset(Left, Right) :-
forall(gen_assoc(Assoc, Left, Value), get_assoc(Assoc, Right, Value)).
Этот предикат будет действителен только в том случае, если левая ассоциация является подмножеством правой ассоциации, как определено выше. Мы можем проверить его и посмотреть, делает ли он то, что мы хотим:
simple(Assoc) :-
empty_assoc(Empty),
put_assoc(foo, Empty, foo_test, V1),
put_assoc(bar, V1, bar_test, Assoc).
complex(Assoc) :-
simple(Assoc1),
put_assoc(baz, Assoc1, bazzle, Assoc).
unrelated(Assoc) :-
empty_assoc(Empty),
put_assoc(baz, Empty, bazzle, Assoc).
...
?- simple(X), complex(Y), association_subset(X, Y).
X = t(foo, foo_test, <, t(bar, bar_test, -, t, t), t),
Y = t(baz, bazzle, -, t(bar, bar_test, -, t, t), t(foo, foo_test, -, t, t)).
?- simple(X), simple(Y), association_subset(X, Y).
X = Y, Y = t(foo, foo_test, <, t(bar, bar_test, -, t, t), t).
?- simple(X), unrelated(Y), association_subset(X, Y).
false.
?- complex(X), simple(Y), association_subset(X, Y).
false.
Мы можем перевести это на ваш точный вопрос так:
left(Assoc) :-
empty_assoc(Empty),
put_assoc(foo, Empty, 1, Assoc).
right(Assoc) :-
left(Assoc1),
put_assoc(bar, Assoc1, 2, Assoc).
?- left(L), right(R), association_subset(L, R), get_assoc(foo, L, Q).
L = t(foo, 1, -, t, t),
R = t(foo, 1, <, t(bar, 2, -, t, t), t),
Q = 1.
Я понимаю, что этот ответ на самом деле не отвечает на заданный вами вопрос, но я надеюсь, что он ответит на вопрос под вопросом. Другими словами, для этих структур данных не требуется особой поддержки - вышеуказанный предикат можно определить и по спискам ассоциаций, вы можете видеть, что все, что вам нужно, это обычные способы создания пустых ассоциаций, добавления, тестирование и генерация ключей/значений ассоциации и базовой структуры данных становится неуместным. Никакая специальная поддержка не нужна ни по структуре данных, ни по унификации. Специальный синтаксис, безусловно, сделает его приятнее смотреть! Но вам не обязательно получать желаемое поведение.
