\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#405: Add Collecting Loops, the 'lmap' and 'dict map' Commands}
\date{July 31, 2012}
\author{Trevor Davel, Donal K. Fellows}
\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 \#405}&\textbf{Add Collecting Loops, the 'lmap' and 'dict map' Commands}\\\hline
Author&

Trevor Davel \tipmail{twylite}{crypt.co.za}
\par
Donal K. Fellows \tipmail{dkf}{users.sf.net}
\\
Created&Tuesday, \(\text{31}^{\text{st}}\) July 2012\\
Type&Project\\
Tcl Version&\(8.6\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.10 $\\
Keywords&Tcl, mapeach, loop, accumulator\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

The \textbf{lmap} command is a collecting loop with the semantics of \textbf{foreach}. When the loop begins an accumulator is set to an empty list. In any iteration where the body of the loop completes normally, the result of the body is appended to the accumulator list. The return value for \textbf{lmap} is the contents of the accumulator. The \textbf{dict map} command is an equivalent collecting loop with the semantics based off \textbf{dict for}.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

\textbf{lmap} arises from a Tcler's Wiki discussion on higher order functions [\url{http://wiki.tcl.tk/26013}]. The construct combines the capabilities of the higher order functions \textit{map} and \textit{filter} with the familiarity and expressive power of Tcl's \textbf{foreach}.

While \textbf{lmap} can be implemented in pure Tcl using \textbf{uplevel} (see the Wiki for examples), substantial performance gains are possible with a bytecode implementation.

\textbf{dict map} was suggested by DKF on tcl-core (2012-08-01) as native dictionary iteration is more efficient that a \textbf{lmap} with two variables).

\section{Proposed Changes}

A new command \textbf{lmap} will be created, with arguments are intentionally very similar to those to \textbf{foreach}:

\begin{quote}
\textbf{lmap} \textit{varname list body}
\end{quote}

\begin{quote}
\textbf{lmap} \textit{varlist1 list1} ?\textit{varlist2 list2 ...}? \textit{body}
\end{quote}

The \textbf{dict} ensemble will be extended with a new sub-command \textbf{map}:

\begin{quote}
\textbf{dict map} \{\textit{keyVar valueVar}\} \textit{dictionary script}
\end{quote}

\subsection{The "lmap" Command}

The \textbf{lmap} command implements a loop where the loop variable(s) take on values from one or more lists, and the loop returns a list of results collected from each iteration.

In the simplest case there is one loop variable, \textit{varname}, and one list, \textit{list}, that is a list of values to assign to \textit{varname}. The \textit{body} argument is a Tcl script. For each element of list (in order from first to last), \textbf{lmap} assigns the contents of the element to \textit{varname} as if the \textbf{lindex} command had been used to extract the element, then calls the Tcl interpreter to execute body. If execution of the body completes normally then the result of the body is appended to an accumulator list. \textbf{lmap} returns the accumulator list.

In the general case there can be more than one value list (e.g., \textit{list1} and \textit{list2}), and each value list can be associated with a list of loop variables (e.g., \textit{varlist1} and \textit{varlist2}). During each iteration of the loop the variables of each varlist are assigned consecutive values from the corresponding list. Values in each list are used in order from first to last, and each value is used exactly once. The total number of loop iterations is large enough to use up all the values from all the value lists. If a value list does not contain enough elements for each of its loop variables in each iteration, empty values are used for the missing elements.

The \textbf{break} and \textbf{continue} statements may be invoked inside body, with the same effect as in the \textbf{for} and \textbf{foreach} commands. In these cases the body does not complete ``normally'' and the result is not appended to the accumulator list.

\subsection{The "dict map" Command}

The \textbf{dict map} command takes three arguments, the first a two-element list of variable names (for the key and value respectively of each mapping in the dictionary), the second the dictionary value to iterate across, and the third a script to be evaluated for each mapping with the key and value variables set appropriately (in the manner of \textbf{lmap}). In an iteration where the evaluated script completes normally (\textit{TCL\_OK}), the script result is put into an accumulator dictionary using the current value of the key variable at that point (having an unset key variable at that point is an error); the result of the \textbf{dict map} command is that accumulator dictionary. Note that it is a deliberate consequence of the above specification that you can change what key a value is mapped to by altering the key variable during the body of the loop.

If any evaluation of the body generates a \textit{TCL\_BREAK} result, no further pairs from the dictionary will be iterated over and the \textbf{dict map} command will terminate successfully immediately. If any evaluation of the body generates a \textit{TCL\_CONTINUE} result, the current iteration is aborted and the accumulator dictionary is not modified. The order of iteration is the order in which the keys were inserted into the dictionary (the ``natural'' iteration order).

(Note that you can view \textbf{dict map} as being to \textbf{dict for} what \textbf{lmap} is to \textbf{foreach}.)

\section{Examples}

Square the values of a list:
\begingroup\small\begin{verbatim}
 set squares [lmap a $list {expr {$a ** 2}}]
\end{verbatim}
\endgroup

Zip lists together:
\begingroup\small\begin{verbatim}
 set zipped [lmap a $list1 b $list2 {list $a $b}] 
\end{verbatim}
\endgroup

Consume several values at once:
\begingroup\small\begin{verbatim}
 set sums [lmap {a b} $values {+ $a $b}] 
\end{verbatim}
\endgroup

Filter a list:
\begingroup\small\begin{verbatim}
 set goodOnes [lmap x $values {expr {[isGood $x] ? $x : [continue]}}] 
\end{verbatim}
\endgroup

Take a prefix from a list:
\begingroup\small\begin{verbatim}
 set prefix [lmap x $values {expr {[isGood $x] ? $x : [break]}}] 
\end{verbatim}
\endgroup

Comparative performance figures:
\begingroup\small\begin{verbatim}
 for {set i 0} {$i < 1000000} {incr i} {
   lappend input [expr { int(rand() * 1000000) }] 
 }
 # Test the performance of [lmap]
 time { apply {{} { 
   set accum 0
   foreach val [lmap i $::input {expr { $i * 5}}] { incr accum $val }
   puts $accum 
 }} } 10
 # Pure Tcl 'Approach #2' implementation from [http://wiki.tcl.tk/26013]
 #   1259118.1 microseconds per iteration
 # C implementation (not bytecode compiled)
 #   1107894.4 microseconds per iteration
 # Bytecode compiled
 #    375085.5 microseconds per iteration
\end{verbatim}
\endgroup

Finding the square root of each of the values in a dictionary, filtering out everything that is not a non-negative number (i.e., outside the domain of the square root operation):
\begingroup\small\begin{verbatim}
 set roots [dict map {k num} $someDict {
     try {
         expr {$num ** 0.5}
     } on error {} {
         continue
     }
 }]
\end{verbatim}
\endgroup

Adjusting the global \textbf{env} array so that all keys are also present as upper-case keys and lower-case values (a not-particularly-useful operation):
\begingroup\small\begin{verbatim}
 array set env [dict map {key val} [dict get env] {
     set key [string toupper $key]
     string tolower $val
 }]
\end{verbatim}
\endgroup

\section{Alternatives}

The name \textbf{mapeach} was originally proposed instead of \textbf{lmap}. However, since Jim Tcl already supports \textbf{lmap} with the same semantics as this TIP proposes, and a pure-Tcl implementation with similar semantics appears on the Wiki [\url{http://wiki.tcl.tk/13920}], this TIP was updated with the change of name. The TIP author favours \textbf{lmap}.

\section{Reference Implementation}

A reference implementation is provided as branch \textit{tip-405-impl-td}. Older revisions are attached to Patch \#3163961 [\url{https://sourceforge.net/support/tracker.php?aid=3163961}]. The implementation leverages the existing \textbf{foreach} infrastructure to provide bytecode support. A test suite is provided.

\section{Thanks}

Thanks to Donal Fellows for suggesting a collecting \textbf{foreach} and providing examples, and to Steve Bennett for suggesting the name \textbf{lmap}.

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

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