Hash tables in prolog

Question

I was solving a puzzle in prolog the other day and realized that were I using another programming language, I would have made use of a hash table/dictionary, but as far as I know this isn't really possible in prolog.

So my first question is are there any prologs that support a dictionary-like data structure with the performance characteristics of a hash table?

Secondly, it occurred to me that since most prologs use a hash table to store predicates, I could write a wrapper predicate to assert and retract facts, creating a dictionary interface which would leverage the underlying hash table of predicates. But would I get the performance characteristics of a hash table, or would the the interface add overheads that would reduce the performance?

Answer 1

Some Prolog environments have Association lists, which can be used to create and edit a dictionary:

• SWI-Prolog
• SICStus Prolog

Edit:

You might be able to get better performance by implementing predicates in foreign languages, for example:

• SWI-Prolog Java or C++
• GNU Prolog C interface
• SICStus C, C++ and Java/.Net.

Answer 2

I'm not a Prolog guy (just an outside observer) but I found this:

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

when I searched for "prolog finite map balanced trees". It says it's an alternative implementation of association lists.

(Why I thought of this: In Haskell, a purely functional language, instead of association lists or hash tables, it is common to use trees for (persistent) dictionaries or finite maps. Lookups are also O(log(N)). See Data.Map for some references on implementing maps with balanced trees.)

Answer 3

In SICStus Porlog, use either the assoc or the avl libraries.