The Curry Challenge

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

The Curry Challenge

Bret Victor
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!)




Reply | Threaded
Open this post in threaded view
|

Re: The Curry Challenge

Petite Abeille

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



Reply | Threaded
Open this post in threaded view
|

Re: The Curry Challenge

Rici Lake-2
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"))


Reply | Threaded
Open this post in threaded view
|

RE: The Curry Challenge

Jerome Vuarand-2
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


Reply | Threaded
Open this post in threaded view
|

Re: The Curry Challenge

Javier Guerra Giraldez
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

Reply | Threaded
Open this post in threaded view
|

RE: The Curry Challenge

Jerome Vuarand-2
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 ?).


Reply | Threaded
Open this post in threaded view
|

Re: The Curry Challenge

Aaron Brown
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/

Reply | Threaded
Open this post in threaded view
|

Re: The Curry Challenge

Romulo Bahiense
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

Reply | Threaded
Open this post in threaded view
|

Re: The Curry Challenge

Mildred Ki'Lya
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       <xmpp:[hidden email]> <http://mildred632.free.fr/>
Clef GPG :    <hkp://pgp.mit.edu> ou <http://mildred632.free.fr/gpg_key>
Fingerprint : 197C A7E6 645B 4299 6D37 684B 6F9D A8D6 [9A7D 2E2B]


Reply | Threaded
Open this post in threaded view
|

Re: The Curry Challenge

Javier Guerra Giraldez
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