MIME-Version: 1.0
References: <905C5ED0-6639-4DEB-95AC-A2FCB2C4491D@gmail.com>
            <AANLkTinSd4KS9gbk_cBPseFjbTFfSmSJUgYJUUP_vpBZ@mail.gmail.com>
            <E8A13BAD-6790-4966-9BAF-379E21DD249C@gmail.com>
            <AANLkTin1PWjtDuxug+ZjGKKg=VBbuz7Pf12rCkAo9+ex@mail.gmail.com>
            <AANLkTinh=zgNFCYWuGwO4mCsL6a7Yezxec264DmWwabk@mail.gmail.com>
            <935A1EA2-C971-4A3A-8DF4-6F890E0CFB32@gmail.com>
            <5256FD2C-CD53-4FF0-A405-5B8B2781E5EC@gmail.com>
            <AANLkTinfC5YVmG57GhGsFAddi1jy7PiZ+6cjV1Wx7KCD@mail.gmail.com>
            <A30A1074-CC53-495E-864C-91180793D8FB@gmail.com>
            <AANLkTi=KxLLEnwJsUzXe9rujQqnFX+rEFWRQq3o=v1_N@mail.gmail.com>
            <19843.17637.935263.780194@morse.mittelbach-online.de>
Content-Type: text/plain; charset=ISO-8859-1
Message-ID:  <AANLkTin649=nq1Rhtttk3vqBD9nNytZ6uO+hU=gcevAw@mail.gmail.com>
Date:         Fri, 18 Mar 2011 09:39:15 -0400
Reply-To: Mailing list for the LaTeX3 project
              <LATEX-L@listserv.uni-heidelberg.de>
Sender: Mailing list for the LaTeX3 project <LATEX-L@listserv.uni-heidelberg.de>
From: Bruno Le Floch <blflatex@GMAIL.COM>
Subject: Re: expl3's seq_pop_right etc.
To: LATEX-L@listserv.uni-heidelberg.de
In-Reply-To:  <19843.17637.935263.780194@morse.mittelbach-online.de>
Precedence: list
Status: R

To be clear, I'm perfectly ready to keep the old interface. I was
mostly concentrating on the implementation, and some functions
appeared more natural than the existing ones in that context.

> > Then there is the issue of l3candidates, which I have not
> > re-programmed yet, as well as the quicksort defined in l3prg.dtx
>
> one step at a time i'd say.

I meant that there are some \seq_from_clist and \clist_from_seq
functions in l3candidates which will have to be rewritten, and a
\seq_quicksort, or something like that, which I haven't looked at. I'm
_definitely not_ rewriting l3prg.dtx :).

>  > - I don't like the fact that \seq_(g)pop return its value locally, so
>  > I changed which functions are provided there to \seq_pop_with:Nn <seq>
>  > {<assignment code>}.
>
> Im not sure here.
>
>  - the general design principle is that all functions that get values from
>    some data structure *always* store them *locally* in a variable.
>
>  - the data structure itself could be local or global and a manipulation of
>    the structure could then be local or global too.

Is there any example of data structure other than seq or prop?


> On the other hand popping + using the value is a quite common usage, so to
> have to always write
>
>   \seq_pop_left_with:Nn \l_foo_seq {\tl_set:Nn \l_bar_tl}
>
> instead of
>
>   \seq_pop:NN \l_foo_seq \l_bar_tl

I see your point. Then perhaps renaming \seq_pop_left_with:Nn to
\seq_pop_left_do:Nn, and leaving \seq_pop:NN as it is could make
sense. Then if we just want to remove the left-most element and apply
some function onto it, we can do

\seq_pop_left_do:Nn \l_foo_seq {\foo:nn {<arg1>}}

and to get a global return value we would do

\seq_pop_left_do:Nn \l_foo_seq {\tl_gset:Nn \g_foo_tl}

Basically, I'm just making an auxiliary function available to the user.

> now having written that I noticed that it isn't true, this is violated in
> l3prop where there are gget functions for key values, so hmmm ... still I
> tend towards the rule above I guess

I think that you are right: there should be a \..._pop_left:NN, which
does something consistent between the various data structures.
Choosing local return values is as good as anything.

> not sure what you mean here. clearly if you loop directly over a sequence
> then using mapping is preferable, but often when you do one element at a time the
> actions are complex so that they don't quite fit into a mapping function

I guess I was just stating the obvious to a TeX programmer: getting
one element in the seq takes a time linear in the length of the seq.
I.e., it is not much faster than mapping on every element. In terms of
efficiency, it is _much_ better to do

\seq_map_inline:Nn \l_foo_seq { <complicated code using #1 spanning
several lines> }

than

\bool_until_do:nn {\seq_if_empty_p:N \l_foo_seq} {
    \seq_pop_left:NN \l_foo_seq \l_foo_tl
    <same complicated code using \l_foo_tl>
}

although the latter is probably clearer.

>  > - I expect the pop_right functions to be much faster for large
>  > sequences than simply storing the elements one by one.
>
> ???

Implementation detail. The naive way of doing things on the right-most
element of the sequence is to remove elements one by one, and store
them in a scratch register, until the last element is reached. That
will be quadratic, and it turned out to be particularly tricky to get
the linear version right. Anyways, unimportant here.


>  > - I'd like every "..._map_function:NN" to become
>  > "..._map_function:Nn", i.e. allow mapping several tokens at a time. It
>
> Personally I don't find this very intuitive; if you map a function you map a
> function name and that would mean N.  Besides you would lose the ability to
> map a constructed function name ie "c" though that is something you would seldom
> need I guess.

My initial application was to be able to map a function with two
arguments on two seq <a> and <b> at the same time. First I zipped the
two seq into one seq whose item each have the form {<a_i>}{<b_i>}.
Then I could map _expandably_

\seq_map_function:Nn \l_foo_zipped_seq {\exp_after:wN \foo_func:nn \use:n}

where the \use:n unbraces its argument. Not a very convincing use.

But Lars Madsen's examples with { \foo_func:nn {arg1} } are better.

> I would rather do
>
>  \cs_new:Npn \map_func:n #1 {<some tokens> \func:n #1}
>  ...map_function:NN \l_foo_seq \map_func:n

That would be better as

...map_inline:Nn \l_foo_seq {<some tokens> \func:n {#1}}

The key here is expandability. When it is not needed, map_inline:Nn
and map_variable:NNn fit the bill nicely. The best might be to leave
both the :NN and :Nn variants, synonyms of each other, hence taking
little of TeX's memory.


There is also the question of whether removing an elements once/all
copies of it should be named as in l3clist or l3tl:

   \clist_remove_element:Nn
   \tl_remove_all_in:Nn
   \tl_remove_in:Nn

I'd go for the tl version.

Regards,
-- Bruno