[Tex/LaTex] Emulate a “tuple” data structure (when you are free to choose the syntax)

data structuresmacrospackage-writing

How can a "tuple" data structure be implemented in LaTeX? The idea is to store several elements (possibly a predefined number) in one macro and then be able to extract each of these elements by index (numeric or otherwise).

\documentclass{article}

% HOW TO IMPLEMENT THIS?
\newcommand{\definetuple}[...]{...}
\newcommand{\extractfromtuple}[...]{...}
% HOW TO IMPLEMENT THIS?

% YOU ARE FREE TO CHANGE SYNTAX HERE
\definetuple{first}{Alice}{Munich}{Germany}
\definetuple{second}{Bob}{London}{United Kingdom}

\begin{document}
  \extractfromtuple{first}{1} lives in \extractfromtuple{first}{2}
  which is located in \extractfromtuple{first}{3};
  this may or may not be true for \extractfromtuple{second}{1}.
\end{document}
% YOU ARE FREE TO CHANGE SYNTAX HERE

I'd like to split the original question so that nice solutions with a new API have a place to live. Should this be community wiki?

Best Answer

\documentclass{article}
\usepackage{xparse}
\ExplSyntaxOn
\NewDocumentCommand{\definetuple}{mmmm}
  {
   \tl_new:c { g_tuple_#1_tl }
   \tl_gset:cn { g_tuple_#1_tl } { {#2} {#3} {#4} }
  }
\DeclareExpandableDocumentCommand{\extractfromtuple}{mm}
  {
   \tl_item:cn { g_tuple_#1_tl } { #2-1 }
  }
\ExplSyntaxOff
\begin{document}
\definetuple{alice}{Alice}{Munich}{Germany}
\definetuple{bob}{Bob}{London}{United Kingdom}

\extractfromtuple{alice}{3}

\extractfromtuple{bob}{1}

\end{document}

In this simple case I've used a token list; for more complex tasks a sequence would be better, perhaps.

Another approach might be with property lists.

\documentclass{article}
\usepackage{xparse}
\ExplSyntaxOn
\NewDocumentCommand{\definetuple}{mmmm}
  {
   \prop_new:c { g_tuple_#1_prop }
   \prop_gput:cnn { g_tuple_#1_prop } { name }    {#2}
   \prop_gput:cnn { g_tuple_#1_prop } { town }    {#3}
   \prop_gput:cnn { g_tuple_#1_prop } { country } {#4}
  }
\DeclareExpandableDocumentCommand{\extractfromtuple}{mm}
  {
   \prop_get:cn { g_tuple_#1_prop } { #2 }
  }
\ExplSyntaxOff
\begin{document}
\definetuple{alice}{Alice}{Munich}{Germany}
\definetuple{bob}{Bob}{London}{United Kingdom}

\extractfromtuple{alice}{country}

\extractfromtuple{bob}{name}

\end{document}

Here the available keys are name, town and country. I'd prefer this approach for more complicated tasks, where, for example, data are added one piece of information at a time; for example one could define

\NewDocumentCommand{\addtotuple}{mmm}
  {
   \prop_gput:cnn { g_tuple_#1_prop } { #2 } { #3 }
  }

and \addtotuple{alice}{town}{Berlin} would move Alice to the north.

Related Solutions

[Tex/LaTex] What are the consideration when choosing either newcommand or newenvironment

Technical reasons for choosing an environment over a command form are that if the definition only involves setting up declarations then it never has to scan the content in advance, so list environments or longtable etc can start typesetting and shipping out pages before the end of the environment is seen. A command form necessarily has to scan to the end of the argument. If there is the possibility of verbatim-like material it is again easier to use an environment form.

Other reasons are mostly just to do with the aesthetics of the document structure you are defining. If you want to think of it as a scoped region define it as an environment. If you want to think of it as a block of text passed to a command, define it as a command.

[Tex/LaTex] How to implement (low-level) arrays in TeX

So, first let me say that this is probably the most thoroughly researched question I've read so far. Congratulations.

I'll be reusing some of David's comments. The hashing algorithm takes the csname as an array of bytes (probably some differences there for XeTeX and LuaTeX, let me focus on 8-bit engines) and computes the sum of csname[i]*2^(len-i) % prime where csname[i] denotes the i-th byte in the csname, len is the total number of characters, and the result is computed modulo the hash prime. The control sequence is then stored or retrieved at the resulting position in the hash table. If there was never any hash collision, then storage and retrieval would be easy and fast, since computing the hash is very fast (additions only). When there is a collision, TeX must check whether the command that it found in the hash table is indeed the csname that was searched for: this is done by comparing strings one character at a time, and is somewhat slower than the hashing algorithm (I think). TeX may need to compare all csnames with the same hash (it can stop once it finds the csname it was looking for).

When comparing strings which happen to be different but have the same hash, TeX goes through them one character at a time, and can stop comparing as soon as it finds a difference: there lies the difference between a long prefix and a long suffix. In scenarios where there are many hash collisions (e.g., with \number), most of the time is spent comparing strings which happen to have the same hash. If such strings differ on an early character (i.e., short prefix), then they will be recognized as different pretty fast. If they have long common prefixes, then TeX will have to scan them for a long time (until the first difference) before it can declare them distinct.

Why is \number bad for hash collisions? Say that your array keys are 5-digit numbers. Compared to the hash of 00000, the hash of abcde (where a, etc, stand for digits) is 16*a+8*b+4*c+2*d+e. For instance, 98765 has the same hashcode as 00000 plus 16*9+8*8+4*7+2*6+5=253. This is tiny. In fact, hash codes for all sets of five digits all lie among 280 possible values! A typical hash value corresponds to more than 300 csnames, and on average TeX will have to test half of them before finding the one it wants.

How do we spread out hashes? The main culprit in having only 280 different values with \number is that Knuth chose a multiplier equal to 2 only. This is justified when names are more or less random sequences of letters of varying length, as in typical TeX documents (adding one character multiplies the whole hash value by 2, so collisions between strings of different lengths are not particularly likely regardless of their internal structure). To choose my encoding, I decided to replace 16*a+8*b+4*c+2*d+e above by 16^4 * a + 16^3 * b + 16^2 * c + 16 * d + e. This is simply done by inserting three dummy characters between each decimal digit, turning 98765 into 9---8---7---6---5. Why insert three rather than more? Because 16 is the smallest power of 2 greater than 10. Choosing 8 instead of 16 would still lead to hash collisions: the hashes of 0--0--0--0--0 and 9--9--9--9--9 are only 9*8^4+9*8^3+...+9=42129 apart, so a typical hash would correspond to two or three csnames.

The last step was simply to convert this to code:

\def\step#1{#1---\step}
\def\endstep#1\step{}
\message{\step 123 \endstep}

Here I use a typical technique to optimize loops: define the looping macro to do what you want and call itself again (here we want #1->#1---), then figure out what to feed as #1 to break the loop. This avoids any test hence is as fast as can be while supporting an arbitrary length of input. Note also that I am putting dashes after the digit (#1--- instead of ---#1) in an effort to put relevant stuff early in the csname.

For the specific application of inserting stuff within numbers, we might be able to do better (haven't benchmarked): numbers will not have more than 10 digits (actually 6 might be a reasonable bound, so remove #6 through #9). The following should work and may be faster

\def\dashes#1#2#3#4#5#6#7#8#9{#1---#2---#3---#4---#5---#6---#7---#8---#9---}
\message{\dashes 123********}

(at least 8 stars after the number, to support numbers of arbitrary lengths between 1 and 10).

Yet another option is to use \romannumeral on each digit, which reduces hash collisions because lengths vary. I don't know how this fares.

One thing is certain: csnames of the form <prefix><varying><postfix> of a constant length can have 256*2^(len-1) different hashes (where len is the length of the varying part), and more realistically 10*2^(len-1) hashes only. Getting 10^5 distinct hashes absolutely requires 10 varying bytes, or some variation on the length of the prefix, varying or postfix parts. In practical settings (where key encoding is taken into account, hence where it is difficult to get more than 10 different leading bytes), one needs about 15 bytes of varying material. My \step approach uses 20 (or 17, depending on whether you count the trailing ---). My \dashes approach may use various numbers depending on whether it is tailored to a specific number length.

Here are ways to implement arrays, depending on your use case. First, let us focus on arrays which can contain arbitrary tokens.

\toks registers. If you are defining and using your array in a controlled environment, use \toks registers within a group. This is limited to 32768 registers (65536 for LuaTeX, I think). Access is faster than csnames, and there is no need for tricks. In fact, this technique can also be used if your array is defined somewhere else in another form, but you need to access it a lot at a given place (within controlled code). This (is|has been) used in l3sort for merge sort.
Multiple \csname approach. This is what you do, and has been discussed at length here. There is no limit in the number of slots, and keys may be other than numeric, but for numeric keys some trickery is needed to avoid hash collisions. Also, you cannot have many such arrays in memory at the same time lest you fill your hash table completely.
A single \csname containing everything. This is essentially what l3prop does at the time of writing. Mapping through all keys is straightforward and fast (per element). Accessing individual elements in an arbitrary order will be very slow, since the whole array needs to be expanded from a macro every time we want to access one element.
Hybrid approaches may be better if your access to given items happens in clusters (e.g., you want to look at keys 1–2000, then 1000–3000, then 2000–4000): you could allocate a certain range of \toks registers for this particular purpose and update once in a while which items are stored in this range. You could also store most stuff in a single csname and only send some items to individual csnames, or toks registers.

Another type of array has numeric values, be it integers, dimensions, and the like.

Various registers can be used in the same way as \toks registers above. A typical example of this is l3regex, which at the time of writing abuses toks, dim, skip, and muskip registers extensively to store all sorts of information. Do not use integer registers, as stuff like \m@ne would break, but expect other stuff to break too (\maxdimen,...). Using dimension or skip or muskip registers can get messy when there is a need to convert from one to the other: of course, we use stretch and shrink components too, which leads to \number\glueshrink\mutoglue\muskip3\relax-type constructions.
A more practical set of numbers is given by the \fontdimen parameters of a font. In effect, those behave like a usual C array whose size must be declared before starting to use it, and whose items are TeX dimens, i.e., integers less than 2^30 in magnitude. All assignments are global. Retrieval speed is comparable to other registers, perhaps a bit slower. See a question I asked on this topic for some other comments.

Of course, the toks, and csname approaches described earlier work fine for numeric data too, but it seems inefficient compared to \fontdimen, especially concerning memory usage (each \fontdimen parameter uses just a few bytes of memory, versus many bytes for the csname and many more for tokens representing the value).

On a similar topic of optimizing data structures:

A long string of characters is stored more efficiently as a csname than as a list of tokens. This has been used at some point in l3fp, storing 10000 decimals of 1/(2pi) as \159154943091895..., to be passed to \string when needed.
Trees which only contain numeric data and only need to be accessed non-expandably can be stored and manipulated as nested boxes, with data stored as various kern nodes for instance. I played with this to implement sorting algorithms some time ago, but the code was messier than the current l3sort and not significantly faster. I'll look at it again some day. It might be possible to reuse this for the relationship between document elements.

Best Answer

Related Solutions

[Tex/LaTex] What are the consideration when choosing either newcommand or newenvironment

[Tex/LaTex] How to implement (low-level) arrays in TeX

Related Question