Хэш-таблицы в прологе

Question

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

Итак, мой первый вопрос: есть ли прологи, которые поддерживают подобную словарю структуру данных с характеристиками производительности хэш-таблицы?

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

Answer 1

Я только что узнал, что:

SWI-Prolog версии 7 вводит dicts как абстрактный объект с конкретного современного синтаксиса и функциональной нотации для доступа пользователей и, а также функции доступа, определенные Пользователь.

Синтаксис выглядит следующим образом:

Tag{Key1:Value1, Key2:Value2, ...}

См Dicts: structures with named arguments для деталей.

Обратите внимание, что:

• These are first-class citizens of the language
• Семантика объединения между dicts может измениться в будущем
• The ./2 оператор, ранее используемый для конс-тов, были переориентированы для доступа пользователей Dict с помощью таких выражений, как point{x:1,y:2}.x
• Dicts can be destructively modified но это не рекомендуется, будучи «нелогичным», не говоря уже о нефункциональном.
• The current underlying implementation является «термином соединение с использованием функтор dict. Первый аргумент является тег. Остальные аргументы создать массив отсортированных пар ключ-значение», таким образом

Пролог догоняет многих языков с «тип карты», который возник в течение последних 10 лет (например, maps in Clojure).

Answer 2

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

• SWI-Prolog
• SICStus Prolog

Edit:

You может быть в состоянии получить bett эр производительность за счет реализации предиката в иностранных языков, например:

• SWI-Пролог Java или C++
• ГНУ Пролог C interface
• SICStus C, C++ и Java/.Net.

Answer 3

Я не парень Пролог (просто сторонний наблюдатель), но я нашел это:

http://www.sics.se/sicstus/docs/4.0.7/html/sicstus/lib_002davl.html

когда я искал «Пролог конечной карты сбалансированных деревьев». В нем говорится, что это альтернативная реализация списков ассоциаций.

(Почему я думал об этом: в Haskell, чисто функциональном языке, вместо списков ассоциаций или хеш-таблиц, обычно используются деревья для (постоянных) словарей или конечных карт. Lookups также O (log (N)). См. Data.Map для получения некоторых рекомендаций по реализации карт со сбалансированными деревьями.)

Answer 4

В SICStus Prolog используйте библиотеки assoc или avl.

Answer 5

Следующие комментарии касаются вашего вопроса в порядке, грубо говоря, от «более конкретного» до «более общего».

Во-первых, обращаясь к ваш конкретный комментарий:

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

Все серьезные реализации Prolog позволяют деструктивно изменять условия Prolog, используя, например, setarg/3. Используя arg/3 и setarg/3, вы получаете доступ O (1) к каждому аргументу термина, которого достаточно для реализации хеш-таблицы точно так же, как на других языках, если ваша система не устанавливает произвольные ограничения на атрибуты терминов.

Это не очень хорошая идея сделать это самостоятельно, так как вы должны учитывать неожиданное копирование и совместное использование терминов на всех условиях. Вместо этого полагайтесь на библиотеки, чтобы сделать это.

Какие библиотеки? Я второй, что другие написали: Вместо хэширования библиотеки, использовать дерева на основе библиотек как library(assoc), library(avl) и т.д. Это не совсем так эффективно, как хэшей в среднем случае, но:

• они часто эффективны достаточно
• они масштабируются очень предсказуемо: наиболее важными операциями являются всегда в O (log (n)).

Кроме того, как пишут другие, деструктивные изменения несовместимы с логикой программирования, а библиотеки деревьев имеют огромное преимущество, что они могут быть реализованы в ISO   Прологе и в чисто   образом с асимптотически оптимальный эффективность.

Наконец, Dict расширение SWI-Prolog являются не ISO совместимой, даже синтаксический не, и, следовательно, не переносится на системы Prolog согласованных с! См. Статью comments Ульриха Ноймеркеля о том, как инфиксная точка может быть добавлена ​​в соответствии с ISO.