The Curry Challenge
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: The Curry Challenge
- From: Bret Victor <bret@...>
- Date: 2007年1月11日 21:01:29 +0000 (UTC)
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!)