# Modeling a mapping from strings to lists of strings in LaTeX3

I'd like to work on a data structure using expl3. This data structure would be read from and written to the .aux file in the following format (this is my proposal—I'm open to better suggestions, of course):

\my@load@command{%
\my@start@key{keyA}%
\my@additem{item1}%
\my@additem{item2}%

(...)

\my@additem{itemn}%
\my@stop@key
\my@start@key{keyB}%
\my@additem{item1}%
\my@additem{item2}%

(...)

\my@additem{itemn}%
\my@stop@key

(...)

\my@stop@key
}


The data structure represented by this code is a mapping from strings to lists-of-strings. In other words, each key is a unique string and is mapped to a list of items, where each item is itself a string (in the sense of LaTeX3's str type). My code is going to ensure that for a given key, all items in the list are unique (but their order matters, therefore this not “set semantic”).

My question is how to model this in the “best way possible” using the current LaTeX3 toolset.

# First possibility

Have a global property list (from l3prop) where each key is mapped to a 〈balanced text〉 that describes the associated list of items using a separator such as \q_nil or a comma (in the latter case, for generality, each 〈balanced text〉 could be of the form {〈item〉},{〈item〉},...,{〈item〉} and be turned into a seq using \seq_set_from_clist:Nn, I suppose).

This means that when an item needs to be added for a given key:

• first, we retrieve the corresponding value as a 〈balanced text〉 token list from our global property list, then convert it to a sequence using either \seq_set_split:Nnn or \seq_set_from_clist:Nn;

• then we append the item to the sequence if it's not already there;

• finally, if this was indeed a new item, we write the resulting list of items to the global property list (as the value associated to the key we are working on).

These operations may be a bit slow, but this method doesn't seem to waste potentially scarce resources such as registers.

# Second possibility

Have a sequence or comma-list to store the list of keys-seen-so-far, and whenever we add a new key to this list, create an associated sequence using something like:

\seq_new:c { g__my_list_of_items_for_ #1 }


where #1 stands for the key name.

This way, manipulating the list of items for a given key is easy, but we create one sequence variable per key seen in the document. There could be, say, a few thousand keys in a given document and, theoretically, several packages might be doing the same. Is this correct use of TeX's resources? For instance, if every seq variable were stored in a TeX register,1 that wouldn't seem very clean to me given the finite number of registers (which may depend on the engine and the precise type of register(s) used for this, but still, if this were the case, I think I found prefer an approach that is only limited by “soft parameters” such as the number of strings, pool size and hash size of the TeX implementation).

Bottom line: the second method has a few advantages, but not knowing how seq variables are implemented in LaTeX3, I have no idea if it scales well.

Footnote

1. I don't know whether this is the case.
• Sequence variables are implemented as macros, no use of registers is made. – egreg Apr 14 '19 at 14:07
• @egreg Thanks, therefore the second solution would seem to be fine? – frougon Apr 14 '19 at 14:09

## 1 Answer

Here's a prototype. Sequences are actually macros, so they only impact the memory for strings and the hash table.

\documentclass{article}
\usepackage{xparse}

\ExplSyntaxOn

\NewDocumentCommand{\keyadd}{mm}
{
\seq_if_exist:cF { g_my_items_for_#1_seq }
{
\seq_gput_right:Nn \g_my_keys_seq { #1 } % the list of keys
\seq_new:c { g_my_items_for_#1_seq }
}
\seq_gput_right:cn { g_my_items_for_#1_seq } { #2 }
}

\seq_new:N \g_my_keys_seq

\cs_generate_variant:Nn \seq_set_split:Nnn { c }

\cs_new_protected:cpn { my@define@key } #1 #2
{
\seq_gput_right:Nn \g_my_keys_seq { #1 } % the list of keys
\__my_key_new:n { #1 }
\seq_set_split:cnn { g_my_items_for_#1_seq } { } { #2 }
}

\cs_new_protected:Nn \__my_key_new:n
{
\seq_new:c { g_my_items_for_#1_seq }
}

\cs_new:Nn \__my_write_key:n
{
\token_to_str:N \my@define@key { #1 }
{
^^J
\seq_map_function:cN { g_my_items_for_#1_seq } \__my_write_item:n
}
^^J
}
\cs_new:Nn \__my_write_item:n { {#1} ^^J }

\AtEndDocument
{
\cs_set_eq:NN \__my_key_new:n \use_none:n
\iow_now:cx { @auxout } { \seq_map_function:NN \g_my_keys_seq \__my_write_key:n }
}

\ExplSyntaxOff

\begin{document}

Some text

\keyadd{keyA}{item1}
\keyadd{keyA}{item2}
\keyadd{keyA}{item3}
\keyadd{keyA}{item4}
\keyadd{keyA}{item5}
\keyadd{keyA}{item6}
\keyadd{keyA}{item7}

\keyadd{keyB}{item1}
\keyadd{keyB}{item2}
\keyadd{keyB}{item3}
\keyadd{keyB}{item4}

\end{document}


The .aux file will contain

\relax
\my@define@key{keyA}{
{item1}
{item2}
{item3}
{item4}
{item5}
{item6}
{item7}
}
\my@define@key{keyB}{
{item1}
{item2}
{item3}
{item4}
}

• Thank you so much! I didn't ask for an implementation, but this way I learnt even more. I wouldn't have had the idea of using \seq_map_function:NN inside the x-type argument of \iow_now:cx, nice trick! (I have to think more about the necessity of \cs_set_eq:NN in the \AtEndDocument hook, but I'll find. :) – frougon Apr 14 '19 at 15:07
• @frougon At end document, the .aux file is read in again and we don't want it executes \seq_new:c anew. Actually, the whole \my@define@key command should be redefined to check whether a new LaTeX run is necessary, by comparing the sequence one gets at that time with the one stored at the beginning (it would be very slow with many such sequences). – egreg Apr 14 '19 at 15:16
• I had understood that, but then I tried a different way which didn't work at first: I tried to replace your \cs_set_eq:NN \__my_key_new:n \use_none:n with \cs_set_eq:NN \my@define@key \use_none:nn. It failed miserably because when the \AtEndDocument hook is tokenized, the @ has catcode 12 (I didn't suspect that under \ExplSyntaxOn régime). Wrapping the whole \AtEndDocument{...} between \catcode\@=11\relax and \catcode\@=12\relax solves this problem. Not claiming it's the most elegant way, but it comforts me in thinking I understood what happens. :) Many thanks! – frougon Apr 14 '19 at 16:05
• @frougon \cs_set_eq:cN {my@define@key} \use_none:nn – egreg Apr 14 '19 at 16:08
• It's indeed perfect. I'll stop thanking you because it's against site policy, etc., but please accept all my thanks in advance and forever. :-) – frougon Apr 14 '19 at 16:12