Curried Lua

wiki

Currying is defined by Wikipedia[1] as follows:

: "In computer science, currying is the technique of transforming a function taking multiple arguments into a function that takes a single argument (the first of the arguments to the original function) and returns a new function that takes the remainder of the arguments and returns the result"

You can implement curried functions in all languages that support functions as first-class objects. For example, there's a little [tutorial about curried JavaScript].

Here is a small Lua example of a curried function:

function sum(number) 
  return function(anothernumber) 
    return number + anothernumber
  end
end

local f = sum(5)
print(f(3)) --> 8

-- WalterCruz

Here is another, contributed by [GavinWraith], which takes a variable number of arguments terminated with a "()":

function addup(x)
  local sum = 0
  local function f(n)
    if type(n) == "number" then
      sum = sum + n
      return f
    else
      return sum
    end
  end
  return f(x)
end

print(addup (1) (2) (3) ())  --> 6
print(addup (4) (5) (6) ())  --> 15

Although these pre-curried functions are useful, what we would really like to do is make a general-purpose function that can perform the curry operation on any other function. To do this, we need to realize that functions can be operated upon by a "Higher-order function" -- a function that takes functions as arguments. The following curry function is an example of this, and curries a 2-argument function:

function curry(f)
    return function (x) return function (y) return f(x,y) end end
end

powcurry = curry(math.pow)
powcurry (2) (4) --> 16
pow2 = powcurry(2)
pow2(3) --> 8
pow2(4) --> 16
pow2(8) --> 256

To go from currying 2 arguments to currying 'n' arguments is a bit more complicated. We need to store an indeterminate number of partial applications, and unfortunately there is no way for Lua to know how many arguments a function requires; Lua functions can successfully receive any number of arguments, whether too many or too few. So, it's necessary to tell the curry function how many single-argument calls to accept before applying those collected arguments to the original function.

(this code is freely available from http://tinylittlelife.org/?p=249 and includes a full discussion of how to tackle this problem.)

-- curry(func, num_args) : take a function requiring a tuple for num_args arguments
--                         and turn it into a series of 1-argument functions
-- e.g.: you have a function dosomething(a, b, c)
-- curried_dosomething = curry(dosomething, 3) -- we want to curry 3 arguments
-- curried_dosomething (a1) (b1) (c1) -- returns the result of dosomething(a1, b1, c1)
-- partial_dosomething1 = curried_dosomething (a_value) -- returns a function
-- partial_dosomething2 = partial_dosomething1 (b_value) -- returns a function
-- partial_dosomething2 (c_value) -- returns the result of dosomething(a_value, b_value, c_value)
function curry(func, num_args)

   -- currying 2-argument functions seems to be the most popular application
   num_args = num_args or 2

   -- no sense currying for 1 arg or less
   if num_args <= 1 then return func end

   -- helper takes an argtrace function, and number of arguments remaining to be applied
   local function curry_h(argtrace, n)
      if 0 == n then
	 -- kick off argtrace, reverse argument list, and call the original function
         return func(reverse(argtrace()))
      else
         -- "push" argument (by building a wrapper function) and decrement n
         return function (onearg)
                   return curry_h(function () return onearg, argtrace() end, n - 1)
                end
      end
   end  
   
   -- push the terminal case of argtrace into the function first
   return curry_h(function () return end, num_args)

end

-- reverse(...) : take some tuple and return a tuple of elements in reverse order
--                  
-- e.g. "reverse(1,2,3)" returns 3,2,1
function reverse(...)

   --reverse args by building a function to do it, similar to the unpack() example
   local function reverse_h(acc, v, ...)
      if 0 == select('#', ...) then
	 return v, acc()
      else
         return reverse_h(function () return v, acc() end, ...)
      end
   end  

   -- initial acc is the end of the list
   return reverse_h(function () return end, ...)
end

The above code is Lua 5.1 compatible.

Since Lua 5.2 (or LuaJIT 2.0) provides an advanced debug.getinfo function that let us know how many arguments a function desires, we can make a practical function which mixes currying and partial application techniques. Here's the code:

function curry(func, num_args)
  num_args = num_args or debug.getinfo(func, "u").nparams
  if num_args < 2 then return func end
  local function helper(argtrace, n)
    if n < 1 then
      return func(unpack(flatten(argtrace)))
    else
      return function (...)
        return helper({argtrace, ...}, n - select("#", ...))
      end
    end
  end
  return helper({}, num_args)
end

function flatten(t)
  local ret = {}
  for _, v in ipairs(t) do
    if type(v) == 'table' then
      for _, fv in ipairs(flatten(v)) do
        ret[#ret + 1] = fv
      end
    else
      ret[#ret + 1] = v
    end
  end
  return ret
end

function multiplyAndAdd (a, b, c) return a * b + c end

curried_multiplyAndAdd = curry(multiplyAndAdd)

multiplyBySevenAndAdd = curried_multiplyAndAdd(7)

multiplySevenByEightAndAdd_v1 = multiplyBySevenAndAdd(8)
multiplySevenByEightAndAdd_v2 = curried_multiplyAndAdd(7, 8)

assert(multiplyAndAdd(7, 8, 9) == multiplySevenByEightAndAdd_v1(9))
assert(multiplyAndAdd(7, 8, 9) == multiplySevenByEightAndAdd_v2(9))
assert(multiplyAndAdd(7, 8, 9) == multiplyBySevenAndAdd(8, 9))
assert(multiplyAndAdd(7, 8, 9) == curried_multiplyAndAdd(7, 8, 9))

Curried Lua

See Also