\HeaderA{funprog}{Common Higher-Order Functions in Functional Programming
Languages}{funprog}
\aliasA{Filter}{funprog}{Filter}
\aliasA{Map}{funprog}{Map}
\aliasA{Reduce}{funprog}{Reduce}
\keyword{programming}{funprog}
\begin{Description}\relax
\code{Reduce} uses a binary function to successively combine the
elements of a given vector and a possibly given initial value.
\code{Filter} extracts the elements of a vector for which a predicate
(logical) function gives true.  \code{Map} applies a function to the
corresponding elements of given vectors.
\end{Description}
\begin{Usage}
\begin{verbatim}
Reduce(f, x, init, right = FALSE, accumulate = FALSE)
Filter(f, x)
Map(f, ...)
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{f}] a function of the appropriate arity (binary for
\code{Reduce}, unary for \code{Filter}, \eqn{k}{}-ary for \code{Map}
if this is called with \eqn{k}{} arguments.
\item[\code{x}] a vector.
\item[\code{init}] an \R{} object of the same kind as the elements of
\code{x}.
\item[\code{right}] a logical indicating whether reduction should proceed
from left to right (left-associative, default) or from right to
left.
\item[\code{accumulate}] a logical indicating whether the successive
combinations should be accumulated.  By default, only the final
combination is used.
\item[\code{...}] vectors.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
If \code{init} is given, \code{Reduce} logically adds it to the start
(when proceeding left to right) or the end of \code{x}, respectively.
If this possibly augmented vector \eqn{v}{} has \eqn{n > 1}{} elements,
\code{Reduce} successively applies \eqn{f}{} to the elements of \eqn{v}{}
from left to right or right to left, respectively.  I.e., a left
reduce computes \eqn{l_1 = f(v_1, v_2)}{}, \eqn{l_2 = f(l_1, v_3)}{}, etc.,
and returns \eqn{l_{n-1} = f(l_{n-2}, v_n)}{}, and a right reduce does
\eqn{r_{n-1} = f(v_{n-1}, v_n)}{}, \eqn{r_{n-2} = f(v_{n-2}, r_{n-1})}{}
and returns \eqn{r_1 = f(v_1, r_2)}{}.  (E.g., if \eqn{v}{} is the
sequence (2, 3, 4) and \eqn{f}{} is division, left and right reduce give
\eqn{(2 / 3) / 4 = 1/6}{} and \eqn{2 / (3 / 4) = 8/3}{}, respectively.)
If \eqn{v}{} has only a single element, this is returned; if there are
no elements, \code{NULL} is returned.  Thus, it is ensured that
\code{f} is always called with 2 arguments.

The current implementation is non-recursive to ensure stability and
scalability.

\code{Reduce} is patterned after Common Lisp's \code{reduce}.  A
reduce is also known as a fold (e.g., in Haskell) or an accumulate
(e.g., in the C++ Standard Template Library).  The accumulative
version corresponds to Haskell's scan functions.

\code{Filter} applies the unary predicate function \code{f} to each
element of \code{x}, coercing to logical if necessary, and returns the
subset of \code{x} for which this gives true.  Note that possible
\code{NA} values are currently always taken as false; control over
\code{NA} handling may be added in the future.  \code{Filter}
corresponds to \code{filter} in Haskell or \code{remove-if-not} in
Common Lisp.

\code{Map} is a simple wrapper to \code{\LinkA{mapply}{mapply}} which does not
attempt to simplify the result, similar to Common Lisp's \code{mapcar}
(with arguments being recycled, however).  Future versions may allow
some control of the result type.
\end{Details}
\begin{Examples}
\begin{ExampleCode}
## A general-purpose adder:
add <- function(x) Reduce("+", x)
add(list(1, 2, 3))
## Like sum(), but can also used for adding matrices etc., as it will
## use the appropriate '+' method in each reduction step.
## More generally, many generics meant to work on arbitrarily many
## arguments can be defined via reduction:
FOO <- function(...) Reduce(FOO2, list(...))
FOO2 <- function(x, y) UseMethod("FOO2")
## FOO() methods can then be provided via FOO2() methods.

## A general-purpose cumulative adder:
cadd <- function(x) Reduce("+", x, accumulate = TRUE)
cadd(seq_len(7))

## A simple function to compute continued fractions:
cfrac <- function(x) Reduce(function(u, v) u + 1 / v, x, right = TRUE)
## Continued fraction approximation for pi:
cfrac(c(3, 7, 15, 1, 292))
## Continued fraction approximation for Euler's number (e):
cfrac(c(2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8))

## Iterative function application:
Funcall <- function(f, ...) f(...)
## Compute log(exp(acos(cos(0))
Reduce(Funcall, list(log, exp, acos, cos), 0, right = TRUE)
## n-fold iterate of a function, functional style:
Iterate <- function(f, n = 1)
    function(x) Reduce(Funcall, rep.int(list(f), n), x, right = TRUE)
## Continued fraction approximation to the golden ratio:
Iterate(function(x) 1 + 1 / x, 30)(1)
## which is the same as
cfrac(rep.int(1, 31))
## Computing square root approximations for x as fixed points of the
## function t |-> (t + x / t) / 2, as a function of the initial value:
asqrt <- function(x, n) Iterate(function(t) (t + x / t) / 2, n)
asqrt(2, 30)(10) # Starting from a positive value => +sqrt(2)
asqrt(2, 30)(-1) # Starting from a negative value => -sqrt(2)

## A list of all functions in the base environment:
funs <- Filter(is.function, sapply(ls(baseenv()), get, baseenv()))
## Functions in base with more than 10 arguments:
names(Filter(function(f) length(formals(args(f))) > 10, funs))
## Number of functions in base with a '...' argument:
length(Filter(function(f)
              any(names(formals(args(f))) %in% "..."),
              funs))
\end{ExampleCode}
\end{Examples}

