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

[Hynek Vychodil]

I propose use stack like perl terminology:

pop x push
unshift x shift

unshift -> Q -> pop
shift     <- Q <- push

On 12/17/07, Raimo Niskanen <raimo+erlang-questions@REDACTED> wrote:
> 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
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>


-- 
--Hynek (Pichi) Vychodil