-- Functional Library
--
-- @file    functional.lua
-- @author  Ikkei Shimomura
-- @date    2005/05/18
--

--
-- map(function, table)
--
-- e.g: map(square, {1,2,3})    -> {2,4,6}
--
function map(func, tbl)
    local newtbl = {}  
        for i,v in pairs(tbl) do
            newtbl[i] = func(v)
        end
    return newtbl
end

-- filter(function, table)
--
-- e.g: filter(isEvent, {1,2,3,4}) -> {1,3}
function filter(func, tbl)
    local newtbl = {}
    for i,v in pairs(tbl) do
        if func(v) then
            table.insert(newtbl, table.getn(newtbl)+1, v)
        end
    end
    return newtbl
end

-- fold_right(function, default_value, table)
--
-- e.g: fold_right(operator.mul, 1, {1,2,3,4,5}) -> 120
function fold_right(func, val, tbl)
    for i,v in pairs(tbl) do
        val = func(val, v)
    end
    return val
end
-- TODO fold_left does same in revese order.


function head(tbl)
    return tbl[1]
end

-- XXX This is bottle-neck for performance.
-- should return the address to next porinter. in C (arr+1)
--
-- e.g  tail({1,2,3}) returns {2,3}
-- 
function tail(tbl)
    if table.getn(tbl) < 2 then
        return nil
    else
        local newtbl = {}
        local tblsize = table.getn(tbl)
        local i = 2
        while (i <= tblsize) do
            table.insert(newtbl, i-1, tbl[i])
            i = i + 1
        end
        return newtbl
    end
end

-- reduce(function, table)
--
-- e.g: reduce(operator.add, {1,2,3,4}) -> 10
function reduce(func, tbl)
    return fold_right(func, head(tbl), tail(tbl))
end

-- curry(f, g)
--
-- e.g: printf = curry(io.write, string.format)
--          -> function(...) return io.write(string.format(unpack(arg))) end
function curry(f,g)
    return function (...)
        return f(g(unpack(arg)))
    end
end


-- Binding argument(s) and generate new function.
-- @see STL's functional, Boost's Lambda, Combine, Bind.
function bind1(func, val)
    return function (v)
        return func(val, v)
    end
end
function bind2(func, val) -- bind second argument.
    return function (v)
        return func(v, val)
    end
end
function bind_first(func, val)
    return function (...)
        return func(val, unpack(arg))
    end
end

-- examples:
-- local mul5 = bind1(operator.mul, 5)
-- > mul5(10) is 5 * 10 = 50
-- local sub2 = bind2(operator.sub, 2) 
-- > sub(20) is 20 - 2 = 18

-- is(checker_function, expected_value)
--
-- return the function to return boolean,
-- if the condition was expected then true, else false.
-- 
-- e.g:
--   local is_table = is(type, "table")
--    print(is_table({}))
is = function(check, expected)
    return function (...)
        if (check(unpack(arg)) == expected) then
            return true
        else
            return false
        end
    end
end

-- local is_even = is(bind2(math.mod, 2), 1)
-- local is_odd = is(bind2(math.mod, 2), 0)


-- operator table.
--
-- lua's operators are not object.
-- so I made it as function object, to pass it as arguments.
-- 
-- @see python's operator module.
operator = {
    mod = math.mod;
    pow = math.pow;
    add = function(n,m) return n + m end;
    sub = function(n,m) return n - m end;
    mul = function(n,m) return n * m end;
    div = function(n,m) return n / m end;
    gt  = function(n,m) return n > m end;
    lt  = function(n,m) return n < m end;
    eq  = function(n,m) return n == m end;
    -- TODO <=, >=, ~= operators
}

-- print(reduce(operator.mul, {1,2,3,4,5}))


-- XXX This _if has bug, when r1 or r2 took expressions as argument.
-- so r1 or r2 will be evaluated what ever condition's value.
-- since Lua does not have macro(maybe?), r1 and r2 should be evaluated lazy.
-- _if = function (cond,r1,r2) if cond then return r1 else return r2 end end 


-- enumFromTo(from, to)
--
-- e.g: enumFromTo(1, 10) -> {1,2,3,4,5,6,7,8,9}
--
-- XXX This does not support lazy evaluation like Haskell.
--     generating big table will be much cost.
-- TODO make it with coroutine.

---
-- operator[(from < to) and "add" or "sub"]
-- 
-- A and B or C as: A ? B : C, A && (B || C) in C/C++
-- I expected, var = if A then B else C end but Lua's if statment does not 
-- return value. var = (function() if A then return B else return C end end)()
-- works, but it too long.
--
-- operator["add"] is syntax suger for operator.add.
-- so if (from < to) is true then the exp will be: bind2(operator.add, 1)
-- that is expand to ...
--  function (v) (function(n,m) return n + m end)(v, 1) end
-- 
-- finally you see that is a function that return incremented value.
--  function (n) return n + 1 end
-- 
 
enumFromTo = function (from,to)
    local newtbl = {}
    local step = bind2(operator[(from < to) and "add" or "sub"], 1)
    local val = from
    repeat 
        table.insert(newtbl, table.getn(newtbl)+1, val)
        val = step(val)
    until (val == to)
    return newtbl
end

-- table.foreach(enumFromTo(1,10), print)


--
-- Combinator in Haskell: ( '.' operator is the combinator )
--      factorial = (foldr (*) 1) . (enumFromTo 1)
--      factorial 10 
--        -> (foldr (*) 1) . (enumFromTo 1 10)
--        -> foldr (*) 1 [1,2,3,4,5,6,7,8,9,10]
--        -> 1 * 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
--        -> 3628800
--
local sum = bind1(reduce, operator.add)
local product = bind1(reduce, operator.mul)

-- complex way to define factorial :p
-- 
-- Python:
-- fact=lambda num: reduce((lambda n,m: n*m), xrange(num+1))
-- 
local factorial = curry(product,curry(bind1(enumFromTo,1),bind2(operator.add,1)))
print(sum({1,2,3,4,5}))
print(product({1,2,3,4,5}))
print(factorial(10))


-- (from Pike's Function.pmod)
--
-- The deaded fixpoint combinator "Y"
--
-- The Y combinator is useful when writting recursive lambdas.
-- It convert a lambda that expects a self-reference as its first argument
-- into one which can be called without this argument.
-- 
-- !!! this code does not work, yet !!!
--[[---------------------------------------------------- Comment out
function Y(f)
    return (function(p)
      return function(...)
        return f(p(p), unpack(arg)) end end)(
            function(p)
              return function(...)
                return f(p(p), unpack(arg)) end end)
end

local fact0 = function(f,n)
  if (n > 1) then
    return n*f(n-1)
  else
    return 1
  end
end
print((Y(fact0))(10))
--]]-----------------------------------------------------------------