Addition of map() and filter().

[André Ericsson <eandre@...>]

I've more than once been struck by lua's lacking tools for handling
"lists", i.e. several values separated by commas in Lua. The problem
is usually when dealing with lists of arbitrary or unknown length, as
expressed by "...". Since this doesn't have a good term (as far as I
know), I'll make one up. I shall call this an expression list in this
post. For example:

function funcThatTakesAnArbitraryNumberOfArgs(...)
    --[[ Manipulates the variable number of arguments in some way. ]]
end

Functions of this kind are often difficult to write and often require
either auxiliary functions that recurse one depth per list item. For
example, if we want to take a variable number of arguments and turn
them all into a string, we can either recursively call tostring(), or
we can create an intermediary table and insert the values there. A
good example is a function in the Lua API from World of Warcraft:

local LOCAL_ToStringAllTemp = {};
function tostringall(...)
    local n = select('#', ...);
    -- Simple versions for common argument counts
    if (n == 1) then
        return tostring(...);
    elseif (n == 2) then
        local a, b = ...;
        return tostring(a), tostring(b);
    elseif (n == 3) then
        local a, b, c = ...;
        return tostring(a), tostring(b), tostring(c);
    elseif (n == 0) then
        return;
    end

    local needfix;
    for i = 1, n do
        local v = select(i, ...);
        if (type(v) ~= "string") then
            needfix = i;
            break;
        end
    end
    if (not needfix) then return ...; end

    wipe(LOCAL_ToStringAllTemp); -- wipe(tbl) removes all entries from tbl.
    for i = 1, needfix - 1 do
        LOCAL_ToStringAllTemp[i] = select(i, ...);
    end
    for i = needfix, n do
        LOCAL_ToStringAllTemp[i] = tostring(select(i, ...));
    end
    return unpack(LOCAL_ToStringAllTemp);
end

As can be seen, manipulating expression lists isn't very easy. I'm
proposing we add two functions to simplify this: map() and filter().

map(func, ...) takes a function and applies it on all of the items in
the expression list, returning them as a new expression list. Example:

function tostringall(...)
    return map(tostring, ...);
end

filter(func, ...) takes a function and calls it for every item in the
expression list, and returns a new expression list consisting of all
the items for which the function returned a true value. Example:

function filterPrimeNumbers(...)
    return filter(isPrime, ...) -- isPrime(n) returns true if n is prime
end

This function doesn't have a good precedent in the wow codebase, but
is commonly used throughout functional programming languages and
programming languages supporting such constructs. Optionally coupled
with a function to generate an expression list from 1 to n, range(n),
it's very easy to generate an expression list of all prime numbers up
to n:

filter(isPrime, range(n)) -- Generates an expression list of all primes up to n

The range() function is not really part of this proposal but is also,
in my opinion, a good addition. I have implemented these three
functions in C as well as in Lua. Limited performance tests show that
for larger expression lists, lua-map() is about 3x slower than
C-map(). For smaller expression lists the difference is roughly 1.5x.
For filter() the performance difference depends on the number of
elements being filtered out. If every element is valid, C-map() was
roughly 15x faster in my testing, down to about 5x if every other
element was filtered out. range() appears to be about 1.5x slower but
both implementations are fast. If desired, I can share my
implementations of these functions.

Regarding use cases, not everyone I've discussed this with over IRC
thinks it's a useful addition to Lua. However, I think the
tostringall() example above alone shows that at least map() has some
very useful use cases. Thoughts?

Best regards,
André Eriksson