Lua Code for Curry (Currying Functions)
This is the Lua code to properly curry (according to the definition I learned, which is supported by Wikipedia) a function in Lua. Mine is a fairly efficient implementation that allows functions to be curried, regardless of how many arguments they would individually take.
My rant on incorrect implementations — several of them very common — follows this listing.
-- Lua implementation of the curry function
-- Developed by tinylittlelife.org
-- released under the WTFPL (http://sam.zoy.org/wtfpl/)
-- 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
-- helper
local function curry_h(argtrace, n)
if 0 == n then
-- reverse argument list and call 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
-- no sense currying for 1 arg or less
if num_args > 1 then
return curry_h(function () return end, num_args)
else
return func
end
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
My Rant About Incorrect Implementations of the Curry Function
When I say “incorrect implementation”, I don’t mean that the function produced an error; I mean that the wrong thing was implemented.
For example, this Functional Library for Lua (which is actually quite good, on the whole) confuses currying with function composition. Reproduced here:
function curry(f,g) – WRONG! this is a COMPOSE function
return function (…)
return f(g(unpack(arg)))
end
end
However, the most common incorrect implementation that I’ve run across is when the programmer confuses currying with a closure. This example kills me: users on the Lua users mailing list have a competition for a curry implementation, and they all do it wrong. Reproduced here:
function curry1 (f,v) – WRONG! this is a CLOSURE function
return function (…) return f(v,…) end
end
function curry (f,v,…) – WRONG! this is a CLOSURE function
if v == nil then return f end
return curry( curry1(f,v), … )
end
A closure can be produced by a curried function (by applying one or more arguments), but closing and currying are 2 separate and distinct operations.
I’ll close this rant by directing it at myself, and talking about some naive implementations of currying (that I wrote). The first one used Lua tables for simplicity:
function curry_bad(func, num_args)
local acc = {} -- accumulate arguments
local function currybad_h(n)
if num_args < n then
return func(unpack(acc))
else
return function(onearg)
acc[n] = onearg
return currybad_h(n + 1)
end
end
end
if num_args > 1 then return currybad_h(1) end
return func -- because no work is required
end
This code is incorrect because there can only be one partial application in use at one time, per curried function — the variable “acc” is shared between all instances. One way around this would be to create a copy of the accumulator at each stage:function curry_inefficient(func, num_args)
-- accumulated args, num args
local function curry_h(acc, n)
if num_args < n then
return func(unpack(acc))
else
return function(onearg)
local newacc = {}
for x = 1, #acc do
newacc[x] = acc[x]
end
newacc[n] = onearg
return curry_h(newacc, n + 1)
end
end
end
if num_args > 1 then return curry_h({}, 1) end
return func -- because no work is required
end
This code produces proper closures, but is inefficient — O(n2) with respect to the number of arguments being curried. Probably not a big deal in practice, but still inefficient. My final implementation (at the top of the page) is O(n) with respect to the number of arguments being curried.
