I was playing with CoffeeScript when I found myself writing the following lines and then looking at them in awe:
compose = (f, g) -> (x) -> f g x
curry = (f) -> (x) -> (y) -> f(x, y)
uncurry = (f) -> (x, y) -> (f x) y
How nice, did I think! Now, as an exercise, I thought I would generalize the curry and uncurry functions to n args, to obtain something similar to this:
curry2 = (f) -> (x) -> (y) -> f(x, y)
curry3 = (f) -> (x) -> (y) -> (z) -> f(x, y, z)
curry4 = (f) -> (x) -> (y) -> (z) -> (t) -> f(x, y, z, t)
And the same thing for uncurry:
uncurry2 = (f) -> (x, y) -> (f x) y
uncurry3 = (f) -> (x, y, z) -> ((f x) y) z
uncurry4 = (f) -> (x, y, z, t) -> (((f x) y) z) t
Writing the n-ary uncurry was not very hard:
uncurry = (n) -> (f) -> (args...) ->
if n == 1
f args[0]
else
((uncurry n - 1) f args.shift()) args...
On the other hand, I can't figure out how to get the n-ary curry to work. I thought of implementing first a curry_list function that is the generalization of this suite:
curry_list2 = (f) -> (x) -> [x, y]
curry_list3 = (f) -> (x) -> (z) -> [x, y, z]
curry_list4 = (f) -> (x) -> (z) -> (t) -> [x, y, z, t]
Here's the implementation:
curry_list = (n) ->
curry_list_accum = (n, accum) ->
if n
(x) ->
accum.push x
curry_list_accum n - 1, accum
else
accum
curry_list_accum n, []
And then I would just compose curry_list with function application to obtain currying. That's what I tried to do:
curry = (n) ->
apply_helper = (f) -> (args) -> f args...
(f) -> compose (apply_helper f), (curry_list n)
But for some reason, it does not work. For exemple, trying to evaluate
curry(3)((a,b,c) -> a + b + c)(1)(2)(3)
yields the following error:
Function.prototype.apply: Arguments list has wrong type
Now after jotting some more notes I understand that trying to compose f with curry_list is incorrect. I do have the intuition that what I'm looking for is something that looks like this composition, but is not exactly that. Am I correct in thinking that?
Finally, what would be a correct implementation?
Source: Tips4all, CCNA FINAL EXAM
You are returning the composed function after curry(3)((a,b,c) -> a + b + c), not the accumulator.
ReplyDeleteThat means ((args) -> f args...) is receiving a function as argument, your code doesn't wait until the argument list is complete to call f.
Maybe implement this without composition?
accumulator = (n, accum, f) ->
return f accum... if n is 0
(x) ->
accum.push x
accumulator n - 1, accum, f
curry = (n) ->
(f) -> accumulator n, [], f
curry(3)((a,b,c) -> a + b + c)(1)(2)(3) # 6
It doesn't look to me like composition. The last curry implementation you have seems to make no distinction between the function to be curried and the arguments to that function, whereas it would seem that such a distinction is rather important. How about something like this?
ReplyDeletecurry = (n, f) ->
acc = []
helper = (x) ->
acc.push x
if acc.length is n then f acc... else helper
A related generalization is presented in Partial with Free Variables.
ReplyDeleteI got really interested in solving this, so I wrote this up. It probably needs a few tweaks, but it works awesomely as far as I have tested. Basically just call f.curry() which returns partially applied functions in succession.. until you call it with the last argument that it takes, which is when that partial calls the one before it and so on, all the way back down the the original f.
ReplyDeletepartial = (f, args1...) -> (args2...) ->
f.apply @, args1.concat args2
partial$ = (f, args) ->
partial.apply @, [f].concat args
Function::curry = (args...) ->
curry$ = (n, f, args...) ->
curry$$ = (n, f, args...) ->
if n > args.length
partial curry$$, (n - args.length), (partial$ f, args)
else f args
curry$$ (n - args.length), (partial$ f, args)
curry$.apply @, [@length, @].concat args
Now we can do things like this:
twoToThe = Math.pow.curry 2
32 == twoToThe 5
32 == Math.pow.curry()(2)(5)
32 == Math.pow.curry()(2, 5)
32 == Math.pow.curry(2, 5)
32 == Math.pow.curry(2)(5)
# And just for laughs:
32 == Math.pow.curry()()()(2)()()()(5)