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))