[erlang-questions] :: : queues (previously: documentation of data structures)

[Raimo Niskanen]

On Mon, Dec 17, 2007 at 01:19:47PM +0100, Andras Georgy Bekes wrote:
> > Elements normally enters the first end and exits the last end.
> >
> > Regular (forward) direction:
> >
> > put_first(Item, Q1) -> Q2
> > get_last(Q) -> Item
> 
> A queue is "FIFO" (First In First Out), so the first element is the one 
> that entered the queue first, and that will leave the queue first.
> 
> Your proposal is the opposite of this. Why?

To get a discussion started ;-)

No you are right, put_last and get_first as regular direction
if you think of a queue of e.g people is more logical.
Or just more logical, period.

But when inventing names for this module for the 3:rd++ time
my head starts spinning. Let me explain the current names,
that I maybe will resort to claim as logical and consistent...

We have a double ended queue, so it should be called dequeue or deq.
But never mind that. The queue is symmetrical, so what is
front/first/left/head or back/last/right/tail is
just a matter of definition.

We have two conflicting API styles:
1) The queue view, inserting and removing items to either end.
   Retrieving values returns both the requested value and
   the new queue with the value removed.
   -> {{value,V},Q2}
   -> {empty,Q1}
   So you typically code:
   case queue:out(Q1) of
       {{value,V},Q2} ->
           {reply,{ok,V},Q2};
       {empty,Q2} ->
           {noreply,Q2}
   end
2) The list view, inserting and removing to either end.
   Retrieving values return just what is requested, so
   a test function is needed if you do not know if the
   queue is empty:
   case queue:is_empty(Q) of
       true ->
           {reply,{ok,queue:head(Q)},queue:tail(Q)};
       false ->
           {noreply,Q}
   end
Believe it or not but 2) is probably faster since data inspection
is fast compared to building the result tuple {{value,_},_}
which gives garbage that has to be collected, eventually.

Queue	Forward		Backwards
	in/1		in_r
	out/1		out_r/1

List	HeadEnd		TailEnd,TailEndReverseName
	cons/1		,snoc/1
	head/1		last/1,daeh/1
	tail/1		init/1,liat/1

If you operate a list as a queue you use cons/1
to enter items and last/1 to retreive elements.
init/1 is for last/1 what tail/1 is for head/1,
that is init/1 returns the list without the
last element, that is; the initial part 
of the list.

Queue operations for list view:
	Forward		Backwards
	cons/1		snoc/1
	last/1,daeh/1	head/1
	init/1,liat/1	tail/1

The daeh/1 and liat/1 are added since snoc/1 felt alone,
so now one might argue last/1 and init/1 are redundant.



> 
> 	Georgy
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB