# The Curry Challenge

10 messages
Open this post in threaded view
|

## The Curry Challenge

 ```I came up with a little Lua problem today, and I thought it would make a fun puzzle for some of you. (My solution is included at the end, so if you want to play, stop reading when I tell you to stop!) Consider this code: function multiplyAndAdd (a,b,c) return a * b + c end multiplyBySevenAndAdd = curry1(multiplyAndAdd,7) assert( multiplyAndAdd(7,8,9) == multiplyBySevenAndAdd(8,9) ) "Curry1" takes a function (eg multiplyAndAdd) and a value (eg 7). It returns a function that is similar to the one it was passed, except that the returned function takes one fewer argument (eg 2 instead of 3). What used to be the first argument (eg "a") is now "frozen" to the given value (eg 7). Our curried function above would be equivalent to: function multiplyBySevenAndAdd (b,c) return 7 * b + c end "Curry1" is pretty easy to write, using 5.1's wacky ... operator: function curry1 (f,v) return function (...) return f(v,...) end end Now, consider this generalization: multiplyBySevenAndAdd = curry( multiplyAndAdd, 7 ) multiplySevenByEightAndAdd = curry( multiplyAndAdd, 7, 8 ) multiplySevenByEightAndAddNine = curry( multiplyAndAdd, 7, 8, 9 ) assert( multiplyAndAdd(7,8,9) == multiplyBySevenAndAdd(8,9) ) assert( multiplyAndAdd(7,8,9) == multiplySevenByEightAndAdd(9) ) assert( multiplyAndAdd(7,8,9) == multiplySevenByEightAndAddNine() ) "Curry" takes a function and an *arbitrary* number of values "n". It returns a function that is similar to the one it was passed, except the returned function takes n fewer arguments. What used to be the first n arguments are "frozen" to the given values, as shown. Challenge #1: Write "curry". (You may assume that none of the values are nil, since nil and ... don't play nice together.) Challenge #2: Write "curry" without using any tables! ;) My solution follows, so stop reading if you're up for the challenges. : : : : : : : : : function curry (f,v,...) if v == nil then return f end return curry( curry1(f,v), ... ) end This is pretty elegant, but it requires one (tail) function call per curried argument. I'm curious whether it's possible to write a "curry" that doesn't create all this indirection. (And doesn't test the length of { ... } and use explicit code for different lengths!) ```
Open this post in threaded view
|

## Re: The Curry Challenge

 ``` On Jan 11, 2007, at 22:01, Bret Victor wrote: ``````I'm curious whether it's possible to write a "curry" that doesn't create all this indirection. (And doesn't test the length of { ... } and use explicit code for different lengths!) `````` Uses the length of the arguments *and* creates tables... 8^) function unpacks( ... ) local someValues = {} for anIndex = 1, select( "#", ... ) do for _, aValue in ipairs( select( anIndex, ... ) ) do someValues[ #someValues + 1] = aValue end end return unpack( someValues ) end function curry( aFunction, ... ) local someArguments = { ... } return function( ... ) return aFunction( unpacks( someArguments, { ... } ) ) end end ```
Open this post in threaded view
|

## Re: The Curry Challenge

 In reply to this post by Bret Victor ``` On 11-Jan-07, at 4:01 PM, Bret Victor wrote: ``````Challenge #1: Write "curry". (You may assume that none of the values are nil, since nil and ... don't play nice together.) `````` ```OK, this one works with nil, but it definitely tests the length of ... and uses different code for different lengths. On the other hand, the different code is not explicit, and the generation is reasonably efficient thanks to Memoize (included below): ``` function Memoise(fn) return setmetatable({}, { __index = function(t, k) local val = fn(k); t[k] = val; return val end, __call = function(t, k) return t[k] end }) end local concat = table.concat Arglist = Memoise( function(n) local t = {} for i = 1, n do t[i] = "a"..i end return function(c) return concat(t, c) end end ) Partial = Memoise( function(n) return loadstring( ``` "return function(f, "..Arglist[n]", "..") return function(...) return f("..Arglist[n]", "..", ...) end end" ``` )() end ) Partial[0] = function(f) return f end function partial(f, ...) return Partial[select("#", ...)](f, ...) end print123 = partial(print, 1, 2, 3) printdcba = partial(print, "d", "c", "b", "a") print123("foo", "bar") printdcba(1, 3) ```---- Here's another application of Arglist, to produce efficient string catenators: ``` Catter = Memoise( function(n) return loadstring( ``` "return function("..Arglist[n]", "..") return "..Arglist[n]"..".." end" ``` )() end ) c6 = Catter[6] print(c6("a", "b", "c", "d", "e", "f")) ```
Open this post in threaded view
|

## RE: The Curry Challenge

 In reply to this post by Bret Victor ```I made 2 versions, one similar to yours, no arrays but recursive, and one using arrays that is not recursive (I don't use argument list length explictly, but through ipairs). Not very interesting, but they are short. -- Recursive without arrays function curry(f, onearg, ...) if not onearg then return f end return curry(function(...) return f(onearg, ...) end, ...) end -- Non-recursive with arrays function curry(f, ...) local cargs = {...} return function(...) local args = {} for _,v in ipairs(cargs) do args[#args+1] = v end for _,v in ipairs({...}) do args[#args+1] = v end return f(unpack(args)) end end ```
Open this post in threaded view
|

## Re: The Curry Challenge

 ```On Thursday 11 January 2007 6:39 pm, Jerome Vuarand wrote: > -- Non-recursive with arrays > function curry(f, ...) > local cargs = {...} > return function(...) > local args = {} > for _,v in ipairs(cargs) do args[#args+1] = v end > for _,v in ipairs({...}) do args[#args+1] = v end > return f(unpack(args)) > end > end i think a worthwhile feature for the next Lua (5.2?) would be to make unpack() accept several arrays and return the list of the concatenation of all. of course, if there's more than one array, there shouldn't be any i,j parameters (who uses those, anyway?). -- Javier ```Attachment: pgpAxL146i5KA.pgp Description: PGP signature
Open this post in threaded view
|

## RE: The Curry Challenge

 ```Javier Guerra wrote: > On Thursday 11 January 2007 6:39 pm, Jerome Vuarand wrote: > > -- Non-recursive with arrays > > function curry(f, ...) > > local cargs = {...} > > return function(...) > > local args = {} > > for _,v in ipairs(cargs) do args[#args+1] = v end > > for _,v in ipairs({...}) do args[#args+1] = v end > > return f(unpack(args)) > > end > > end > > i think a worthwhile feature for the next Lua (5.2?) would be > to make unpack() accept several arrays and return the list of > the concatenation of all. of course, if there's more than > one array, there shouldn't be any i,j parameters (who uses > those, anyway?). I tried a version with a proxy table referencing the two argument list arrays, but unpack doesn't seem to call metamethods. It could be a nice addition to have an alternative base library which is slower but use metamethods. Also I second your proposed unpack with multiple arrays (unpackm for unpack multiple ?). ```
Open this post in threaded view
|

## Re: The Curry Challenge

 In reply to this post by Javier Guerra Giraldez ```Javier wrote: ``````i think a worthwhile feature for the next Lua (5.2?) would be to make unpack() accept several arrays and return the list of the concatenation of all. `````` I think I've wanted this functionality before (and I presumably just rolled my own like Jerome did). ``````of course, if there's more than one array, there shouldn't be any i,j parameters `````` I suppose unpack could check its arguments' types, but that seems a bit ugly. ``````(who uses those, anyway?). `````` They're necessary for arrays with embedded nils: ``````-- Returns a function that prints MakePrinter's arguments: function MakePrinter(...) `````` local Args = {...} local ArgCount = select("#", ...) return function() print(unpack(Args, 1, ArgCount)) end end `````` Printer = MakePrinter(nil, "b", nil, nil) Printer() ``````nil b nil nil Here's another use: ``````-- Returns an iterator that goes through all Len-long -- subsequences of Arr: function Subseqs(Arr, Len) `````` local Pos = 0 return function() Pos = Pos + 1 if Pos + Len - 1 <= #Arr then return unpack(Arr, Pos, Pos + Len - 1) end end end `````` Nums = {"one", "two", "three", "four", "five", "six"} for Val1, Val2, Val3, Val4 in Subseqs(Nums, 4) do `````` print(Val1, Val2, Val3, Val4) end ``````one two three four two three four five three four five six (Plug: both examples are from Beginning Lua Programming.) -- Aaron Beginning Lua Programming: http://www.amazon.com/gp/product/0470069171/ ```
Open this post in threaded view
|

## Re: The Curry Challenge

 In reply to this post by Bret Victor ```Bret Victor wrote: (...) ``````Challenge #1: Write "curry". (You may assume that none of the values are nil, since nil and ... don't play nice together.) Challenge #2: Write "curry" without using any tables! ;) ``````(...) ```That's a bit difficult to do in plain Lua, because you can't return multi values from a function and next to it return others values from another function : ``` f=function() return 1,2,3 end print(f(),f()) > 1 1 2 3 And if you can't do that, and can't use tables, well... ```The only solution I can think about, Rici already suggested, that is to create on the fly a function (using loadstring) that receives n parameters and return a closure that will return those n parameters plus the closure's varargs. ``` Something like: function(f,a0,a1,a2,~~,an) return function(...) return f(a0,a1,a2,~~,an,...) end end ("~~" means "..." as in math, not in Lua) ```As the challenge didn't say anything about doing only on lua side or not... (untested, but using an almost identical code in production ) ``` static int l_unwrap(lua_State L) { int i = 1; while(lua_type(L,lua_upvalues(i))!=LUA_TNONE) { lua_pushvalue(L,lua_upvalue(i)); lua_insert(L,i); /* First param first */ i++; } return lua_call(L,lua_gettop(L)-1,LUA_MULTRET); } int l_wrap(lua_State *L) { /* A sanity check here would be good */ lua_pushcclosure(L,l_unwrap,lua_gettop(L)); return 1; } ... lua_register(L, "wrap", l_wrap) ... f = wrap(print,1,2,3) f(4,5,6) > 1 2 3 4 5 6 Pretty simple, uh? --rb ```
 In reply to this post by Javier Guerra Giraldez ```Le jeu 11/01/2007 Ã 18:52 Javier Guerra Ã Ãcrit: > > there shouldn't be any i,j parameters (who uses those, anyway?). > me, I use those i, j parameters. Very useful for nil tables or when you want to unpack just a part of an array. Anyway, it is still possible to provide the i, j parameters and the multiples table parameters at the same type just by checking the type of parameters. Table or number -- Mildred Clef GPG : ou Fingerprint : 197C A7E6 645B 4299 6D37 684B 6F9D A8D6 [9A7D 2E2B] ```
 ```On Saturday 13 January 2007 8:51 am, Mildred wrote: > Anyway, it is still possible to provide the i, j parameters and the > multiples table parameters at the same type just by checking the type > of parameters. Table or number yep, that was my idea. the limitation would be that when you specify several arrays you can't specify a range. of course, using two different functions would be easier; but not as nice -- Javier ```Attachment: pgpJMY1GRvsEY.pgp Description: PGP signature