# Most efficient way to reverse a token list (tail recursion)

Goal: reverse a list of characters, going from \def\mylist{abcdefgh} to \def\mylist{hgfedcba}. This is easy using a marker which does not appear in the list, such as \relax:

\def\mylist{abcdefgh}
\def\reverse #1%
{\edef #1{\expandafter \reverseloop #1\relax \marker }}
\def\reverseloop #1#2\marker
{\ifx#1\relax\reverseend\fi \reverseloop #2\marker #1}
\def\reverseend #1\marker #2{}
\reverse\mylist
\show\mylist


So far, so good. Unfortunately, this wastes a large amount of memory, and trying to apply the same function when \mylist has a few thousand characters already blows up. Indeed, each call to \reverseloop reads the whole token list as its #2 argument, and this is not flushed from TeX's memory via tail recursion, because TeX never reaches the end of the replacement text of \reverseloop, or rather, only reaches it at the very end, once all the \reverseloop macros have been expanded. You can see this from the call trace in

\def\fiveup{\edef\mylist{\mylist\mylist\mylist\mylist\mylist}}
\fiveup \fiveup \fiveup \fiveup
\tracingall
\reverse\mylist


Thus, the whole process consumes a memory proportional to the square of the number of characters, reaching millions, typical size of TeX's main memory. How can I implement such a reversal using only a linear amount of memory?

It should easily scale up to 100000 characters, albeit maybe be a bit slow there: of course we cannot avoid a quadratic time. I don't care too much about expandability.

-
I'm not sure that such a beast really exists, unless you can index the string: \def\i{a}\def\ii{b}\def\iii{c}\iii\ii\i. That is, index the string via macros and expand them from the last back. Of course it's not "linear". – egreg Nov 24 '11 at 12:09
You can look at page 379 in the TeXbook – egreg Nov 24 '11 at 12:13
@BrunoLeFloch Your title implies speed, but your text is about memory use. Could you clarify one or the other? – Joseph Wright Nov 24 '11 at 13:01
What's wrong here with using two macros and moving tokens one at a time? Slow for long lists, but would be the usual approach. – Joseph Wright Nov 24 '11 at 13:04
@egreg Joseph rightfully pointed out that my title was misleading. I guess that a more interesting question would be "what are the most efficient ways (plural) to reverse a string?". I've been experimenting with many approaches. Expandably, I cannot do better than O(n^2) time and O(n) space (but I wouldn't be too surprised to see a crazy divide-and-conquer algorithm in O(n log n)). Non-expandably, I can reach linear times for token lists <32768 chars long (by storing the various characters in TeX's toks registers, in a group). – Bruno Le Floch Nov 24 '11 at 13:40

\def\firstoftwo#1#2{#1}
\def\secondoftwo#1#2{#2}

\def\rev#1#2\revA#3\revB{%
\if\relax\detokenize{#2}\relax
\expandafter\firstoftwo
\else
\expandafter\secondoftwo
\fi{#1#3}{\rev#2\revA#1#3\revB}}

\edef\x{\rev abcde\revA\revB}\show\x


A string with 10000 characters is reversed in about 20 seconds on my machine, without clobbering the memory.

8.16 real         5.16 user         0.05 sys


(just because I had to react to \show)

In #3 there is the "reversed-so-far" string; at each step of the recursion I put in front of it the first token in the remaining string, which is #1#2. When #2 is empty, the recursion ends.

The "linear" reversing should be obtained by

\catcode\@=11
\def\reverse#1{\count@=\z@\def\temp{}
\expandafter\doreverse#1\doreverse
\loop\ifnum\count@>\z@
\edef\temp{\temp\csname @@\romannumeral\count@\endcsname}%
\repeat
\expandafter\def\expandafter#1\expandafter{\temp}%
}
\def\doreverse#1{%
\unless\ifx#1\doreverse
\expandafter\def\csname @@\romannumeral\count@\endcsname{#1}%
\expandafter\doreverse
\fi}
\catcode\@=12


which is limited only by available memory, using the space for control sequences.

With \def\mylist{<string>}, \reverse\mylist defines successively \i, \ii and so on to the tokens forming the list and at the end stores them back in reverse order in \temp to which \mylist is then made equivalent. So after

\def\mylist{abcdefgh}
\reverse\mylist


\mylist will expand to hgfedcba. It doesn't work as is for braced groups, but the modification in that case should be trivial.

I've reversed a 40000 character long string in 42 seconds. TeX refuses to do a 100000 character long string, because it exhausts the pool size. (I removed \begingroup and \endgroup as it makes run away of save size.)

-
How are the braces in the elements to be preserved? \edef\x{\rev {a}bcd{e}\revA\revB} – Ahmed Musa Nov 25 '11 at 1:23
@AhmedMusa You can say \unless\ifnum\pdfstrcmp{\detokenize{#1}}{\string\doreverse\space} instead of \ifx#1\doreverse (requirese pdftex; in xetex use \strcmp instead of \pdfstrcmp; or input pdftexcmds.sty and use \pdf@strcmp). – egreg Nov 25 '11 at 1:30
Changing \count@ outside a local group is dangerous! – Ahmed Musa Nov 25 '11 at 1:39
(1) I don't see how \unless\ifnum\pdfstrcmp{\detokenize{#1}}{\string\doreverse\space} preserves outer braces in the reserved elements. The braces are lost during argument grabbing, not inside \doreverse. (2) \doreverse is not expandable: not interesting. (3) \doreverse might define 10000k temporary commands, unless they're localized. – Ahmed Musa Nov 25 '11 at 1:47
@AhmedMusa Yes, the braces are lost, but an additional test might reinsert them. Localizing the definitions would rapidly exhaust the save size. It's just an exercise: reversing long strings is better done with a different program. – egreg Nov 25 '11 at 11:01

I didn't check the memory, but a lua solution would be:

\def\StrRev#1{\directlua{tex.print(string.reverse('#1'))}}

abcdefgh\par
\StrRev{abcdefgh}


Which prints:

I measured the running time of two string lengths. On my machine:

Using \nullfont

100 000 chars : 0.21 s
1 000 000 chars : 1.24 s

With font

100 000 chars : 0.74 s
1 000 000 chars : 6.21 s

-
1) Please post a minimal working example. 2) \luacode should be replaced by \luaexec if you use the luacode package. 3) otherwise: nice solution – topskip Nov 24 '11 at 12:18
sorry, but I cannot see how this is a good answer? the question was tagged tex-core.. – Davy Landman Nov 24 '11 at 12:33
@DavyLandman This site is also good for future reference - and perhaps someone with a similar problem using LuaTeX sees this question and finds the related and constructive answer by Marco. I welcome such answers (I tend to give LuaTeX solutions, too :)) – topskip Nov 24 '11 at 12:36
@Patrick \luaexec doesn't seem to be defined in plain LuaTeX. It throws Undefined control sequence. I changed example to ConTeXt. – Marco Nov 24 '11 at 12:48
@DavyLandman Yes, this answer does not help me much, but it may very well be of interest to others. – Bruno Le Floch Nov 24 '11 at 13:47

Here is an expandable solution that preserves outer braces and order of entries:

\documentclass{article}
\makeatletter
\let\xp\expandafter
\@ifdefinable\leftbracechar\relax
\edef\leftbracechar{\xp\@gobble\string\{}
\newcommand*\ifstrsame[2]{%
\ifnum\pdfstrcmp{#1}{#2}=\z@\xp\@firstoftwo\else
\xp\@secondoftwo\fi
}
\newcommand*\ifleftbrace[1]{%
\ifstrsame{\detokenize\xp{\@gobble#1.}}{}\@secondoftwo{%
\ifstrsame{\xp\@car\detokenize{#1}\@nil}\leftbracechar
\@firstoftwo\@secondoftwo
}%
}
\begingroup
\catcode\&=3
\gdef\preservebracereverse#1{\pr@reverse{}&#1\@nnil}
\gdef\pr@reverse#1#2\@nnil{%
\pr@rev@rse{#1}{\xp\ifleftbrace\xp{\@gobble#2}}#2\@nnil
}
\gdef\pr@rev@rse#1#2&#3{%
\xp\ifx\@car#3\@nil\@nnil\xp\@firstoftwo\else\xp\@secondoftwo\fi
{\unexpanded{#1}}
{#2{\pr@reverse{{#3}#1}}{\pr@reverse{#3#1}}&}%
}
\endgroup
\makeatother

% Example:
\edef\x{\preservebracereverse{{ax}bcd{ey}}}
\show\x

\begin{document}

\end{document}

-

Warning, this would take approximately 7 minutes to run, if you expand the list \XXX rather than \ABC as shown in the minimal below:

\documentclass{article}
\usepackage{lipsum}
\edef\ABC{So far, so good. Unfortunately, this wastes a large amount of memory, and trying to apply the same function when mylist has a few thousand characters already blows up. Indeed, each call to reverseloop reads the whole token list as its 2 argument, and this is not flushed from TeX's memory via tail recursion, because TeX never reaches the end of the replacement text of reverseloop, or rather, only reaches it at the very end, once all the reverseloop macros have been expanded. You can see this from the call trace in.So far, so good. Unfortunately, this wastes a large amount of memory, and trying to apply the same function when mylist has a few thousand characters already blows up. Indeed, each call to reverseloop reads the whole token list as its 2 argument, and this is not flushed from TeX's memory via tail recursion, because TeX never reaches the end of the replacement text of reverseloop, or rather, only reaches it at the very end, once all the reverseloop macros have been expanded. You can see this from the call trace in.\par}
\edef\X{\ABC\ABC\ABC\ABC\ABC\ABC\ABC\ABC\ABC\ABC\ABC\ABC\ABC\ABC\ABC\ABC\ABC}
\edef\XX{\X \X \X \X}
\edef\XXX{\XX\XX}
\makeatletter
\begin{document}
\makeatletter
\let\stack\@empty
\def\element{#1}%
\push@element
}
\def\push@element{%
\xdef\stack{\element\space \stack}
}
\newcounter{cnt}
\expandafter\@tfor\expandafter\next\expandafter:\expandafter=\ABC \do{%
\stepcounter{cnt}
}
\stack

\thecnt

\end{document}


It reverses 116552 characters over 60 pages. I used \edef to store the list. I iterate over the list using LaTeX \@tfor and then pushed it onto a stack. When the stack is expanded it prints the list in reverse.

A real TeXnical solution for the list as presented would be to put the letters in a box one letter wide and then split the box in a loop.

The best solution would be to sort the list as you capture the letters, i.e, before you insert them in the list.

-

I am not sure about the tail recursion, but maybe:

\catcode@=11
\input lambda.sty
\catcode@=12
\Show\Reverse[a,b,c,d,e,f,g,h] % => [h,g,f,e,d,c,b,a]
\bye


could be of interest here (lambda.sty).

-

## protected by Joseph Wright♦Mar 13 '15 at 13:39

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).