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

Question

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.

Answer 1

\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.

For your list I get

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}%
    \advance\count@\m@ne
  \repeat
  \expandafter\def\expandafter#1\expandafter{\temp}%
}
\def\doreverse#1{%
  \unless\ifx#1\doreverse
    \advance\count@\@ne
    \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.)

Answer 2

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

Answer 3

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} 

Answer 4

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\add@element#1{%
  \def\element{#1}%
  \push@element
}
\def\push@element{%
   \xdef\stack{\element\space \stack}
}
\newcounter{cnt}
\expandafter\@tfor\expandafter\next\expandafter:\expandafter=\ABC \do{%
  \add@element{\next}
  \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.

Answer 5

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).