\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#136: Large List Initialisation}
\date{May 25, 2003}
\author{Simon Geard}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#136}&\textbf{Large List Initialisation}\\\hline
Author&

Simon Geard \tipmail{simon.geard}{ntlworld.com}
\\
Created&Sunday, \(\text{25}^{\text{th}}\) May 2003\\
Type&Project\\
Tcl Version&\(8.5\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.5 $\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP proposes the addition of a list initialisation command so that large lists can be easily and efficiently initialised.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

With the advent of the \textit{lset} command in Tcl 8.4 it seems to me that we need a method of efficiently initialising large lists that can then be used as areas of preallocated memory. From a users point of view it can be much easier to preallocate say a 1000 element array and then use \textit{lset} and \textit{lindex} to manipulate it than using \textit{lappend} to build it up. Having posted the idea to the tcl-core mailing list various alternatives were suggested to create a list of 1000 x characters:
\begin{enumerate}
\item{}
\textit{lappend} in a loop
\begingroup\small\begin{verbatim}
 unset -nocomplain s
 for {set i 0} {$i < 1000} {incr i} {lappend s {x}}
\end{verbatim}
\endgroup
\setcounter{enumi}{1}
\item{}
\textit{split}ting of a string
\begingroup\small\begin{verbatim}
 set s [split [string repeat x 1000] ""]
\end{verbatim}
\endgroup
\setcounter{enumi}{2}
\item{}
Direct construction of the string form
\begingroup\small\begin{verbatim}
 set s x[string repeat " x" 999]
\end{verbatim}
\endgroup
\end{enumerate}

None of these is particularly satisfactory. (1) seems inefficient since there are 1000 lappend operations, (2) is not general enough since it doesn't generalise to more than one character and (3) doesn't actually create a list. (2) and (3) also suffer from the problem that they are not at all obvious to new users and do nothing to dispel the notion that ``everything is a string'' in Tcl.

\section{Implementation}

I propose the introduction of a new command, \textit{lrepeat}:
\begingroup\small\begin{verbatim}
 lrepeat <number> <element1> ?<element2>? ?<element3>? ...
\end{verbatim}
\endgroup

which returns a list of length \tiplangle{}number\tiprangle{} * (number of elements). The new list is the given element sequence repeated \tiplangle{}number\tiprangle{} times. \tiplangle{}number\tiprangle{} must be a positive integer and each \tiplangle{}element.\tiprangle{} a list or string.

Examples:
\begingroup\small\begin{verbatim}
 lrepeat 100 0                 - returns a list of 100 zeros
 lrepeat 100 [lrepeat 100 0]   - returns a 100x100 matrix (list of lists) of zeros
 lrepeat 3 a b c               - returns a nine-element list {a b c a b c a b c}
 lrepeat 1 a b c               - identical to [list a b c]
\end{verbatim}
\endgroup

\section{Reference Implementation}

I have implemented this command. A patch against the Tcl 8.4.3 source, which implements the command and provides both tests and documentation, is available from \url{http://homepage.ntlworld.com/whiteowl/tcl/tcl843-lrepeat.patch} The directory also contains timing information and code which demonstrates a performance gain of over ten times for large lists.

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\end{document}
