-- Save global environment in g and start functional namespace
local g = _G
module('functional')
 
-- Raise an error if the given object is not of the required type
local function require_type(o, t)
	if g.type(o) ~= t then
		g.error("Required type " .. t .. " but got " .. g.type(o), 1)
	end
end
 
-- Concatenates two arrays
local function concat(lhs, rhs)
	require_type(lhs, "table")
	require_type(rhs, "table")
 
	local result = {}
	local i = 0
	for _, a in g.ipairs({lhs, rhs}) do
		for _, v in nipairs(a) do
			i = i + 1
			result[i] = v
		end
	end
 
	return result
end
 
-- Converts the given sequence into an expression list that can be used
-- with the generic for. If the given sequence is a wrapped iterator
-- it is unwrapped. If it is a table it is passed to the given iterator
-- or ipairs if no default iterator was specified.
local function to_iter(sequence, default_iter)
	if sequence.iter then return g.unpack(sequence) end
	default_iter = default_iter or g.ipairs
	return default_iter(sequence)
end
 
-- 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](#sequence).
function wrap_iter(func, invariant, control)
	return { func, invariant, control, iter = true }
end
 
-- 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 nipairs(arr)
	require_type(arr, "table")
	local upper = g.table.maxn(arr)
	return function(a, i)
		i = i + 1
		if i <= upper then
			return i, a[i]
		end
	end, arr, 0
end
 
-- Returns the given arguments as an array with an additional field, n, which
-- includes the number of elements in the array. This is helpful when the given
-- argument list contains nils which termiante array iteration (with ipairs).
local function to_args(...)
	return { n = g.select('#', ...), ... }
end
 
-- Returns a new table that maps each key, k, to the result of f(value) for
-- all keys in the given [sequence](#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](#wrap_iter).
--
-- Example: map(f, { k1 = v1, k2 = v2, ..}) -> { k1 = f(v1), k2 = f(v2), ... }
function map(func, seq)
	require_type(func, "function")
	require_type(seq, "table")
 
	local result = {}
	for k, v in to_iter(seq, g.pairs) do
		result[k] = func(v)
	end
 
	return result
end
 
-- 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 reduce(func, init, seq)
	require_type(func, "function")
	require_type(seq, "table")
 
	local result = init
	for _, v in to_iter(seq)  do
		result = func(result, v)
	end
 
	return result
end
 
-- 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](#sequence). It is
-- best to use this when comparing elements is expensive.
--
-- [Schwartzian Transform]: http://en.wikipedia.org/wiki/Schwartzian_transform
function sort_by(func, seq)
	require_type(func, "function")
	require_type(seq, "table")
 
	local result = map(function (v) return { func(v), v } end, seq)
	g.table.sort(result, function (l, r) return l[1] < r[1] end)
	return map(function (v) return v[2] end, result )
end
 
-- Sentinel used to indicate a parameter must be filled in with partial(...).
PLACEHOLDER = {}
g.setmetatable(PLACEHOLDER, { __tostring = function() return "PLACEHOLDER" end })
 
-- 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 partial(func, ...)
	require_type(func, "function")
 
	local args = to_args(...)
	local arg_iter = wrap_iter(nipairs(args))
	if false == reduce(function(a, v) return a or (v == PLACEHOLDER) end, false, arg_iter) then
		return func(g.unpack(args, 1, args.n))
	end
 
	return function(...)
		-- TODO: make this functional
		local args = copy(args) -- This prevents side-effects
		local myargs = to_args(...)
		for i = 1, args.n do
			if args[i] == PLACEHOLDER then
				args[i] = g.table.remove(myargs, 1) or PLACEHOLDER
			end
		end
 
		return partial(func, g.unpack(concat(args, myargs), 1, args.n + myargs.n))
	end
end
 
-- 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 curry(func, arity, ...)
	require_type(func, "function")
	require_type(arity, "number")
 
	local args = { n = g.select('#', ...), ... }
	for i = args.n + 1, arity do
		g.table.insert(args, PLACEHOLDER)
	end
 
	return partial(func, g.unpack(args))
end
 
-- Takes a function and a [sequence](#sequence) and returns a new array containing only values
-- where `func(value)` is `true`.
function filter(func, seq)
	require_type(func, "function")
	require_type(seq, "table")
 
	local result = {}
	for _, v in to_iter(seq) do
		if func(v) then
			g.table.insert(result, v)
		end
	end
 
	return result
end
 
-- Returns a shallow copy of the given [sequence](#sequence)
function copy(seq)
	return map(function(x) return x end, seq)
end
 
-- Adds all public functions and variables for this module to the given environment.
-- An error will be raised if this would cause an existing key in the given
-- environment to be written. Passing `true` to `force` will skip this check.
--
-- A common way to use this is: `functional.add_to_env(getfenv())`
function add_to_env(env, force)
	force = force or false
	for k, v in g.pairs(g.getfenv()) do
		if not (g.string.match(k, "^_.*") or k == "add_to_env") then
			if env[k] then
				error("Key collision for key '" .. k .. "'", 2)
			end
			env[k] = v
		end
	end
end