Hashset and Queue in prolog

Question

I need to make a hashset and my first thought is to use an associative list or a dictionary. However the lookup and insert procedures have O(logN) complexity. Is there a faster way to do it?
I also need a queue. I found an implementation here which uses difference lists but I'm wondering if there is something better.

Answer 1

The queue in the answer, to the question you linked, it looks fine to me. What do you mean by "something better"?

EDIT: and here is a link to a hash-table implementation in Prolog.

About a hash table, this is now a matter of definition. What do you mean by "make a hashset"? and why do you think you would use a ready data structure?

You have at least three options:

1. use an existing key-value data structure (check out library(assoc) and the SWI-Prolog dict) and don't care how it is implemented;
2. implement a data structure to your exact specifications;
3. do not use a data structure defined in Prolog, and use the database instead through assert* and retract*.

We don't know (from your question) if you must implement a hash table for your "hashset"; or if you think you need something with the word "hash" in it, or if you want something that is usually implemented as a hash table in other languages and you have just used the word "hashset" but you don't need a particular property specific to hash tables. Which one is it?

From your question:

Is there a faster way to do it?

No one knows. It is unknowable. You need a use case, then you need to write a few tests for that use case, then you need to profile your implementations and measure time (and memory?). You can then compare them to each other or to a Java HashSet, for example. Until then, it is all just speculation.

If you want to go with option 2. and implement a data structure with properties of a hash table, you'd have to do it yourself.

If you need help with deciding how to implement a hash function or how to make an array in Prolog, you should ask more specific questions.

If you need help with deciding what is the best option for you (one of the three above or something else), you need to ask more specific questions.

Just very briefly about arrays in Prolog. Many of the predicates are documented in the section on Term manipulation.

You can use a Prolog term to make an array. For example, this is an array of size 5, with the atoms [a,b,c,d,e] in it:

array(a, b, c, d, e)

You can get the element at an index using arg/3:

?- A = array(a, b, c, d, e), arg(3, A, X).
A = array(a, b, c, d, e),
X = c.

You can re-assign a value at an index using the *setarg predicates.

?- A = array(a, b, c, d, e), arg(3, A, X), setarg(3, A, hello), arg(3, A, Y).
A = array(a, b, hello, d, e),
X = c,
Y = hello.

Getting and setting using arg and setarg should be constant-time operations.

If you have a more specific question you'll have to ask.