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

[Raimo Niskanen]

If changing the names of daeh, in_r, lait, snoc, init, out_r, head, tail
and cons, why not change them all?

Proposed new API (along the lines of Anders Ramsell's suggestion:

Introduce the notion of a first .. last order in the queue.
Elements normally enters the first end and exits the last end.

Regular (forward) direction:

put(Item, Q1) -> Q2
put_first(Item, Q1) -> Q2
get(Q) -> Item
get_last(Q) -> Item
drop(Q1) -> Q2
drop_last(Q1) -> Q2

So put/2 is an alias for put_first/2,
get/1 is an alias for get_last/1
and drop/1 is an alias for drop_last/1.

Goofy (backward) direction:

put_last(Item, Q1) -> Q2
get_first(Q) -> Item
drop_first(Q1) -> Q2

Inspection:

is_empty(Q) -> Bool
len(Q) -> Length

Creation and conversion:

new() -> Q
from_list(List) -> Q
to_list(Q) -> List

Operations:

join(Q1, Q2) -> Q3
split(N, Q1) -> {Q2, Q3}

Questionables (so list-like there will be no end to it...):

delete(Item, Q1) -> Q2
  should it be
delete(fun/1, Q1) -> Q2
  or
zf(fun/1, Q1) -> Q2
  aka
filtermap(fun/1, Q1) -> Q2
  or maybe
search(fun/1, Q) -> {Position,Item} | false
delete(Position, Q1) -> Q2
  where search/2 could be replaced with
fold(fun/2, Q, Start) -> Term

I also aim to add new(Q1) -> Q2 that converts to a new queue format
containing length so on a converteed queue len/1 is O(1), but
once you have called new/1 you can not code downgrade or send nor
save a queue term to be understood by an older node.

One can also consider to rename the whole module to deq, but that name
should perhaps be reserved for a large and complicated all operations
O(1) double ended queue according to Kaplan/Tarjan...



On Sun, Dec 16, 2007 at 10:02:56PM +0100, Robert Virding wrote:
> I quite agree! First it should be liat, if it is supposed to be the reverse
> of tail.
> 
> Then I also agree even more that the whole naming of the functions in the
> queue module sucks. It was probably originally taken from Okasaki who uses a
> subset of it in a chapter of his book. I personally think it can only be
> considered as a form of "in joke" which is really only comprehensible to
> people who know the terminology and as such is not suitable for a general
> library.
> 
> I find it easier and faster to rewrite the code than try and remember the
> functions names if I need a queue. The algorithm is basically quite simple
> and neat.
> 
> Rewrite the module with good names for the API and make sure to drop the old
> names from the documentation to make sure they don't spread, though they
> will have to be kept for BC. Get out a new version ASAP.
> 
> Robert
> 
> P.S. Yes I know I occasionally include small jokes there are limits to what
> you can do.
> 
> On 14/12/2007, Anders Ramsell <anders@REDACTED> wrote:
> >
> > > > Anyways, queue:lait/1 should be liat/1 shouldn't it? Both in
> > > > the doc and impl. (It is the opposite of tail. The opposite of
> > > > cons/2 is snoc/2, the opposite of head/1 is daeh/1 but
> > > > lists:reverse("tail") /= "lait").
> > >
> > > Oh yes!!! I was tired when I wrote it, then self-blind, and
> > > nobody proofread. If I get a reason to touch the module I will
> > > add liat/1, forget about lait/1 but keep it around for backwards
> > > compatibility...
> >
> > (I'm going to stick my neck out now. Hope I don't get beheaded.)
> >
> > I think the API of the queue module is a mess. Full of weird
> > names and functions that do the same thing. Quite unlike most
> > other modules in stdlib. This is a pity because this module is
> > very useful. Or at least it could be - I'll get back to that.
> >
> > If you're going to change it - change it a lot. My suggestion
> > would be something along these lines. First remove a few
> > functions.
> >
> > Function:  Duplicate of:
> > ------------------------
> > daeh       last
> > in_r       cons
> > lait       init
> > snoc       in
> >
> > But we still have some weird names left. How do you 'init' a
> > queue by removing something from it? And out_r isn't all that
> > beautiful either. Then we have 'head' as the opposite of 'last'.
> >
> > I would rename those and a few more to get something that I think
> > look like a "consistent" naming.
> >
> > Function:  Rename to:
> > ---------------------
> > init       drop_last
> > out_r      out_last
> > head       first
> > tail       drop_first
> > cons       in_first
> >
> > Of course all the old names would have to remain for a few
> > versions for backwards compatibility reasons.
> >
> >
> > Now back to what I hinted at before. The names of the API are
> > important but what they do is of course much more important and
> > the API is quite complete. But one, in my opinion, very important
> > function is missing. This fact has kept me from using this module
> > and roll my own on more than one occasion. There is no function
> > that removes a specified item no matter where in the queue it is.
> > Sometimes you just get tired of queueing.
> >
> > No matter what you think of the rest of this mail please add that
> > function. Keeping to my own suggested names it could be called
> > 'drop'. I know it can't be O(1) but that doesn't matter.
> >
> > Well? Will I know get pummeled into my shoes like the noob I am
> > or do I have a point?

You sure do have point.



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

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

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB