Implementation of a queue 
Author Message
 Implementation of a queue

Hi!

I would like to know how to implement a queue in prolog without using
a list. I can't find anything on the web and none of the books I have
suggest how to do it.

This is what I would like to do:

Have rules that specify the ability to create a queue and then add
elements to it. It will then take another rule to tell me the length of
the queue. How do I maintain a Data Structure like this in prolog?

After I add an item I want to print out the entire queue with the item.

It would be nice to delete an item in the queue also.

Please Help in whatever way possible.

ADTMan

Sent via Deja.com http://www.*-*-*.com/
Before you buy.



Sat, 10 May 2003 03:00:00 GMT  
 Implementation of a queue
I can't think of a good reason to do this, but...
asserta/1,retractz/1 is the only place I can think of to start, although I
think you may need to get tricky if you want backtracking enabled. You might
need to create something for adding that does asserta on it's way in and
retracta on its way out and vice versa with the removal(z, of course) and
I'm not sure if this is guaranteed to work. But it is possible to write an
accumulating pred akin to findall that counts as opposed to building a list.

Mind you, I'm just a newbie, so take this with a grain of salt.
It also depends on which prolog you're using, who knows, someone may be
including it as a base type(shudder). I keep seeing infinite loops.

Geoff

Quote:

> Hi!

> I would like to know how to implement a queue in prolog without using
> a list. I can't find anything on the web and none of the books I have
> suggest how to do it.

> This is what I would like to do:

> Have rules that specify the ability to create a queue and then add
> elements to it. It will then take another rule to tell me the length of
> the queue. How do I maintain a Data Structure like this in prolog?

> After I add an item I want to print out the entire queue with the item.

> It would be nice to delete an item in the queue also.

> Please Help in whatever way possible.

> ADTMan

> Sent via Deja.com http://www.deja.com/
> Before you buy.



Sun, 11 May 2003 13:14:05 GMT  
 Implementation of a queue

Quote:

> Hi!
> I would like to know how to implement a queue in prolog without using
> a list. I can't find anything on the web and none of the books I have
> suggest how to do it.
> This is what I would like to do:
> Have rules that specify the ability to create a queue and then add
> elements to it. It will then take another rule to tell me the length of
> the queue. How do I maintain a Data Structure like this in prolog?
> After I add an item I want to print out the entire queue with the item.
> It would be nice to delete an item in the queue also.

1. you might try using a `difference list' as a queue.
2. this does not work completely, because difference lists will allow
   you to dequeue elements from an empty queue ...
[this far is described in Sterling and Shapiro]
3. to solve that problem, simply keep a counter as part of your queue
   datastructure (this trick is attributed to Mark Johnson, I believe)

in short:

empty_queue(q(0,X,X)).
enqueue(El, q(N,Hd,[El|T2]),   q(s(N),Hd,T2)).
dequeue(El, q(s(N),[El|T0],T), q(N,T0,T)).

--
Gertjan van Noord Alfa-informatica, RUG,  Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl            http://www.let.rug.nl/~vannoord



Sun, 11 May 2003 03:00:00 GMT  
 Implementation of a queue

Quote:

> 1. you might try using a `difference list' as a queue.
> 2. this does not work completely, because difference lists will allow
>    you to dequeue elements from an empty queue ...

It can be very useful to dequeue elements from an empty queue. Think of them
as "promises" which may or may not need to block its user until the promise
is redeemed (i.e. when the sufficient elements have been queued"

WF Clocksin



Sun, 11 May 2003 03:00:00 GMT  
 Implementation of a queue

Quote:


>> 1. you might try using a `difference list' as a queue.
>> 2. this does not work completely, because difference lists will allow
>>    you to dequeue elements from an empty queue ...
> It can be very useful to dequeue elements from an empty queue. Think of them
> as "promises" which may or may not need to block its user until the promise
> is redeemed (i.e. when the sufficient elements have been queued"

I agree. In fact in joint work with Dale Gerdemann on an implementation of
finite state transducers enriched with predicates and identity constraints
(between input and output) we use exactly this technique.  However, wouldn't
it be appropriate to have a different name for such a datastructure? Its
certainly not a `normal' queue...

Gj

--
Gertjan van Noord Alfa-informatica, RUG,  Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl            http://www.let.rug.nl/~vannoord



Sun, 11 May 2003 03:00:00 GMT  
 Implementation of a queue

Quote:

> Hi!

> I would like to know how to implement a queue in prolog without using
> a list. I can't find anything on the web and none of the books I have
> suggest how to do it.

> This is what I would like to do:

> Have rules that specify the ability to create a queue and then add
> elements to it. It will then take another rule to tell me the length of
> the queue. How do I maintain a Data Structure like this in prolog?

The alternative to use lists is to use functors. This is in fact the
basic data structure in Prolog.

For example, you can describe a queue like:

- 0-ary functor "empty" is a queue, representing an empty queue.
- binary functor queue(Q, X) is a queue, where Q is a queue and X an
element.

A "type-checker" prolog predicate for such queue is:

queue(empty).
queue(queue(Q,X)) :-
        queue(Q).

DO NOT confund the queue/2 functor with the queue/1 predicate.

In Prolog you can't "create" an empty queue, instead you describe a
predicate which is true when a queue is empty, and by unification a
variable will be instantiated with an empty queue. In this
implementation is very simple.

empty_queue(empty).

For the rest you will make your homework.

I guess it's possible to get more efficient queue implementations in
Prolog using functors.

Sorry for the english mistakes.

+ Gustavo +



Fri, 16 May 2003 03:00:00 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. efficient implementations of priority queues

2. Implementation of a QUEUE

3. CLASSes and QUEUEs (was: Re: QUEUE in QUEUE)

4. Question: amortized complexity of Queue implementation

5. Queue implementation

6. Priority Queue Implementation

7. Persistent Queue implementations?

8. How to make a queue of queue's

9. Clarification of Queue Operation / Behavior when using multiple Queues

10. Queue in Queue?!

11. Queue of Queues problem.

12. QUEUE in QUEUE

 

 
Powered by phpBB® Forum Software