Lua Functional

lua-functional provides a set of higher-order functions typically found in functional languages.

Concepts

Sequences

This library provides several functions that work with a sequence. A sequence as defined by this library is something that can be iterated over. A Lua table is a sequence and can be passed to any function that accepts a sequence. In addition, it is possible to use a “wrapped iterator” as a sequence. A wrapped iterator allows a custom iterator to be used instead of a table.

As a contrived example, you may want to concatenate a sparse array of strings into a single string. In Lua, the end of the array is inidcated by a nil value, so the traditional array iterator, ipairs, would stop concatenation as soon as an element in the array is nil. However, you can use a custom iterator to achieve the desired effect:

local array = { 'a', 'b', 'c', nil, 'e' }
local sequence = functional.wrap_iter(functional.nipairs(array))
local concatenate = function(t, v) return v and t .. v or t end
local result = functional.reduce(concatenate, "", sequence)
print(result)

results in:

abce

The example above uses a custom iterator from the functional module, nipairs, which iterates through a spare array until it hits the last index. The iterator is “wrapped” with wrap_iter, which creates a single object that can be passed as a sequence to a higher-order function.

Tables vs. Arrays

In Lua the most basic data structure is a table, not a list as in most functional languages. Most higher-order functions in this project treat sequences as arrays. That is, they are treated as if they have a well-defined order (determined by numeric index), the values of non-numeric keys are ignored, and the keys are not passed to functions.

Only where specifically stated do higher-order functions use tables as an unordered collection of key/value pairs.

Function Reference

function wrap_iter(func, invariant, control)

Wraps an expression list that can be used with a generic for loop. This wrapped list can be used as an argument to any higher-order function that takes a sequence.

function nipairs(arr)

Returns an expression list (iterator function, invariant, control variable) which can be used with generic for to iterate, in order, over all array indices, including those that are nil, as in a sparse array. Like ipairs, iteration starts at index 1 and will not occur over non-numeric fields.

Behavior is undefined if an element is added to the table during iteration. Updating an existing key is allowed. If a key that has not yet been visited is removed then it will still be included in the iteration, with a nil value.

Performance is O(n), though it will be slower than using ipairs.

function map(func, seq)

Returns a new table that maps each key, k, to the result of f(value) for all keys in the given sequence. By default, this will iterate over the sequence as a table, not as an array. This behavior can be changed by passing a wrapper iterator.

Example: map(f, { k1 = v1, k2 = v2, ..}) -> { k1 = f(v1), k2 = f(v2), … }

function reduce(func, init, seq)

Returns a value computed by applying a function to an accumulation value and each array element in turn. The evaluation is left to right. If seq is empty then the init value is returned.

function sort_by(func, seq)

Returns a a copy of seq sorted using func. This method uses the Schwartzian Transform instead of traditional comparison of elements. Func is evaluated for each element and the resulting value is used to sort the sequence. It is best to use this when comparing elements is expensive.

function partial(func, …)

Given a function and and a set of partially filled parameters (use functional.PLACEHOLDER to indicate a parameter that must be filled)), this method will return a function that will accept the remaining placeholders before executing the passed in function. This is essentially specialization of the given function. For example, you could create a specialization of math.pow that returns powers of 3 as follows:

threeToThePowerOf = partial(math.pow, 3, placeholder)

You could then call threeToThePowerOf like this:

threeToThePowerOf(2) -> 9
threeToThePowerOF(4) -> 81

function curry(func, arity, …)

Given a function, the arity for the function, and an incomplete set of arguments (for example, 2 arguments supplied to a function with an arity of 3), this function will return a new function that uses the supplied argument and only requires the remaining arguments. Arguments are filled from left to right. This is a specialization of partial(…).

function filter(func, seq)

Takes a function and a sequence and returns a new array containing only values where func(value) is true.

function copy(seq)

Returns a shallow copy of the given sequence

function trace(func, name, out)

Returns a new function that when called will first write all arguments passed in before executing the passed in function. This method will use tostring(func) as the name of this function unless name is defined. This method will use io.stdout unless out is defined.