Functional Library

wiki

 -- Functional Library
 --
 -- @file functional.lua
 -- @author Shimomura Ikkei
 -- @date 2005年05月18日
 --
 -- @brief porting several convenience functional utilities form Haskell,Python etc..

 -- map(function, table)
 -- e.g: map(double, {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(is_even, {1,2,3,4}) -> {2,4}
 function filter(func, tbl)
 local newtbl= {}
 for i,v in pairs(tbl) do
 if func(v) then
	 newtbl[i]=v
 end
 end
 return newtbl
 end

 -- head(table)
 -- e.g: head({1,2,3}) -> 1
 function head(tbl)
 return tbl[1]
 end
 -- tail(table)
 -- e.g: tail({1,2,3}) -> {2,3}
 --
 -- XXX This is a BAD and ugly implementation.
 -- should return the address to next porinter, like in C (arr+1)
 function tail(tbl)
 if table.getn(tbl) < 1 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

 -- foldr(function, default_value, table)
 -- e.g: foldr(operator.mul, 1, {1,2,3,4,5}) -> 120
 function foldr(func, val, tbl)
 for i,v in pairs(tbl) do
 val = func(val, v)
 end
 return val
 end
 -- reduce(function, table)
 -- e.g: reduce(operator.add, {1,2,3,4}) -> 10
 function reduce(func, tbl)
 return foldr(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

 -- bind1(func, binding_value_for_1st)
 -- bind2(func, binding_value_for_2nd)
 -- @brief
 -- Binding argument(s) and generate new function.
 -- @see also STL's functional, Boost's Lambda, Combine, Bind.
 -- @examples
 -- local mul5 = bind1(operator.mul, 5) -- mul5(10) is 5 * 10
 -- local sub2 = bind2(operator.sub, 2) -- sub2(5) is 5 -2
 function bind1(func, val1)
 return function (val2)
 return func(val1, val2)
 end
 end
 function bind2(func, val2) -- bind second argument.
 return function (val1)
 return func(val1, val2)
 end
 end

 -- is(checker_function, expected_value)
 -- @brief
 -- check function generator. return the function to return boolean,
 -- if the condition was expected then true, else false.
 -- @example
 -- local is_table = is(type, "table")
 -- local is_even = is(bind2(math.mod, 2), 1)
 -- local is_odd = is(bind2(math.mod, 2), 0)
 is = function(check, expected)
 return function (...)
 if (check(unpack(arg)) == expected) then
 return true
 else
 return false
 end
 end
 end

 -- operator table.
 -- @see also 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;
 le = function(n,m) return n <= m end;
 ge = function(n,m) return n >= m end;
 ne = function(n,m) return n ~= m end;
 }

 -- enumFromTo(from, to)
 -- e.g: enumFromTo(1, 10) -> {1,2,3,4,5,6,7,8,9}
 -- TODO How to lazy evaluate in Lua? (thinking with coroutine)
 enumFromTo = function (from,to)
 local newtbl = {}
 local step = bind2(operator[(from < to) and "add" or "sub"], 1)
 local val = from
 while val <= to do
 table.insert(newtbl, table.getn(newtbl)+1, val)
 val = step(val)
 end
 return newtbl
 end

 -- make function to take variant arguments, replace of a table.
 -- this does not mean expand the arguments of function took,
 -- it expand the function's spec: function(tbl) -> function(...)
 function expand_args(func)
 return function(...) return func(arg) end
 end

TODO: YCombinator, IteratorChain?, ...

Sample codes

 local product = bind1(reduce, operator.mul)
 local sum = expand_args(bind1(reduce, operator.add))
 -- @see Python: fact=lambda num: reduce((lambda n,m: n*m), xrange(num,0,-1))
 -- @see Haskell: fact = (foldr (*) 1) . (enumFromTo 1)
 local factorial = curry(product,bind1(enumFromTo,1))