Частичный словарь / Объединение записей?

Question

Я понимаю, что некоторые прологи поддерживают словарь-ассоциативные структуры данных из коробки. Для реализаций, которые это делают, они поддерживают некоторое понятие частичной унификации с другой структурой, которая фактически не содержит все ключи?

Например, в синтаксисе core.logic/miniKanren:

(run* [q]
  (== {:foo 1 :bar 2} (partial-map :foo q)))

Это вернет единственный результат, где q связан с 1.

Прологи дают этой операции или этой частичной структуре имя?

Answer 1

Некоторые системы Prolog, такие как Eclipse, имеют запись записи. Это может быть использовано, когда вы заранее знаете возможные ключи вашей карты. Но для этого нужно объявление типа. Запись обозначения также встречается на языках-потомках Пролога, таких как Erlang.

Идея очень проста. Сначала вы объявляете тип записи (здесь изобретен некоторый синтаксис):

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

до свидания

Answer 2

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

Я понимаю, что этот ответ на самом деле не отвечает на вопрос, который вы задали, но я надеюсь, что он отвечает на вопрос под вопросом. Другими словами, не требуется специальной поддержки для этих структур данных - вышеупомянутый предикат может быть определен также и для списков ассоциаций, вы можете видеть, что все, что вам нужно, это обычные способы создания пустых ассоциаций, добавление, проверка и генерация ключей / значений ассоциации и базовой структуры данных становится неактуальной. Никакой специальной поддержки не требуется ни в отношении структуры данных, ни в отношении унификации. Специальный синтаксис определенно сделает его более привлекательным! Но это не обязательно, чтобы получить желаемое поведение.

Answer 3

Мне не очень понятно, чего вы на самом деле хотите (вы удалили аспект хеширования), но, может быть, вы скорее хотите использовать термины или структуры объектов?

Они популярны у лингвистов и были частью жизни.

Их можно реализовать с помощью атрибутивных переменных, но до сих пор я не видел особого спроса на них.

Вы также можете смоделировать их с помощью синтаксического объединения. Это неуклюже, потому что вам нужно представлять каждую функцию отдельным аргументом (вы можете сделать это немного лучше, но тогда это будет сложнее). Поэтому, если ваша программа содержит n функций, структура объектов будет содержать n различных аргументов, большинство из которых никогда не будут затронуты. Тем не менее, объединение будет работать напрямую, как и предполагалось.