Arc Forumnew | comments | leaders | submitlogin
There's currying and then there's currying...
6 points by cchooper 4594 days ago | 12 comments
The spectre of currying is haunting the forum once again. I still think its a good idea for Arc, but only if we use the right kind of currying.

True currying, in the mathematical sense (as used in ML, O'Caml etc.) works as follows: if f is a function of 3 arguments and f' is the curried form, then:

  f(x, y, z) = f'(x)(y)(z)
or in Arc:

  (f x y z) = (((f' x) y) z)
As Loup pointed out in his post, some kind of association would be required to make that practical:

  (f' x y z) => (((f' x) y) z)
Note that currying a function always produces a unary function, which in turn produces a value or another unary function, and so on. If your original function took n arguments, then you must call your curried version n times* to get the final value.

In ANSI Common Lisp, pg defined a different way to do currying:

  (defun curry (fn &rest args)
    #'(lambda (&rest args2)
         (apply fn (append args args2))))
Note that this takes a function of many arguments, and returns a 'curried' version of many arguments, which also returns a function of many arguments, which returns a final value. So you always call the 'curried' function twice to get your value, regardless of the number of arguments.

So this isn't really currying at all. It's something else, something useful, but not currying in the true sense.

Now as people have pointed out, true currying simply doesn't work with variadic functions, because n is unknown at the time you curry your function. On the other hand, the pg style of currying works fine with any function. It has a downside: you always get your final value after the second call, so you can't gradually build up the arguments over many calls, but then does anyone really ever do that, and if you do, can't you just use the curry function again?

So I think if Arc is going to have any kind of currying, it should have pg currying. I've suggested that if you use a [...] form without any underscores in it, then the function should be automatically pg-curried:

  (+ a b c d e) = ([+ a b] c d e)
I think this is a very concise notation and I'd use it quite often.

Oh, and if you want to do real currying, here's a macro I created that does that with fixed-arity functions. The functions automatically associate to the left. I've hastily translated this from Lisp into Arc so it may have a few bugs:

  (mac cfn (parms . body)
    `(curry ,(len parms) (fn ,parms ,@body)))

  (def curry (parms-length fn (o old-args))
    (rfn curried new-args
         (withs (args (join old-args new-args)
                 args-length (len args))
                (if (no new-args) curried
                    (is args-length parms-length) (apply fn args)
                    (> args-length parms-length) (err "Too many arguments.")
                    (curry parms-length fn args)))))


* I know you're not really applying the arguments to the same function each time, but to the function returned by the function returned by etc. etc., but I couldn't think of an easy way to express that.


6 points by tokipin 4594 days ago | link

personally i don't see why the insistence on a remainder-style curry. i like what i proposed in the other thread http://arclanguage.org/item?id=3962 which is that if a function is given _ as an argument, even in multiple places, then the function will be curried for those argument slots

  (= my-prn (print _ 0 _ 0))

  (my-prn "test" 1) => (print "test" 0 1 0)
the benefit is you don't require what i think is a somewhat arbitrary arrangement of placing the most important arguments at the end, and you don't need to use argument-swapping functions just to line things up correctly. you just put the _ into the argument spots you want to postpone and you're done

for variadics:

  ((+ a b _) c d e) => (+ a b c d e)

-----

4 points by cchooper 4594 days ago | link

That also looks useful to me, but to be pedantic, I wouldn't call it currying.

-----

4 points by cchooper 4594 days ago | link

Do you mean something like this?

  (mac fix rest
    (withs (rest-parm (if (is '_ (last rest)) (uniq))
            parms rest-parm
            body nil
            rev-rest (if rest-parm (cdr (rev rest)) (rev rest)))
           (trav rev-rest 
                 (fn (x) (if (is '_ (car x))
                             (w/uniq u (push u parms) (push u body))
                             (push (car x) body)))
                 [self (cdr _)])
           `(fn ,parms ,(if rest-parm 
                            (join (list 'apply) body (list rest-parm))
                            body))))
If so I'm going to push it to the wiki.

-----

1 point by tokipin 4594 days ago | link

actually i don't understand any of that ^_^;; i'm a lisp noob. in other languages there aren't macros so i implement it as a function which stores the function-to-be-curried and its initial arguments in a closure

however i tested your macro with some arithmetic and it all seems to work fine. the only thing i found is that something like this will cause an error:

  ((fix + _ 2) 3 4)
because there isn't an underscore at the end. i don't understand lisp enough to see if that was your intention. i think for the sake of variadic functions it should adapt regardless of where the underscore is (or whether or not it's present, eg: (fix +)), either by detecting if a function is variadic (which i'm guessing isn't reasonably possible at the moment) or by always returning a variadic function [edit: actually i think i can decipher the meaning of (if (is '_ (last rest))]

if the generated expression is always variadic, it would seem to mess with the fact that the underlying system cares how many arguments there are. is that a big deal? i don't think so. a language i use this function in is Lua, whose functions are all variadic (in that the interpreter doesn't complain if you supply too few (unsupplied are niled) or too many (excess are discarded) arguments) and it simply is never a problem. to me the fixed-argument thing seems similar in spirit to static typing in that it tries to solve a problem that really isn't significant

-----

2 points by cchooper 4594 days ago | link

Yes, I implemented it so it would only be variadic if there was an underscore at the end. It would actually be a simpler macro if they were always variadic, but that's such a radical change to the language that I'm a bit wary about it.

But maybe it's a good idea. I see your point about the 'spirit of static typing'. I'll have to check out Lua and see how it works out.

Edit: I mean it would be radical if fix were implicit, of course.

-----

7 points by almkglor 4594 days ago | link

Done. On the arc-wiki.git, as lib/bracket-curry.arc

-----

5 points by raymyers 4594 days ago | link

I was skeptical, but I tried it out.

    (map [+ 1] li) ; does the same as the Haskell
     map (+ 1) li
But this has the added bonus of being able to sensibly curry variadic functions like + and map.

    (map [+ 1] '(1 2 3 4) '(1 2 3 4))  =>  (3 5 7 9)
    (apply [map +] '((1 2) (1 2) (1 2)))  =>  (3 6)
I'm sold :)

-----

2 points by almkglor 4594 days ago | link

([apply [map +]] '((1 2) (1 2) (1 2)))

-----

2 points by cchooper 4594 days ago | link

Genius

-----

3 points by ecmanaut 4594 days ago | link

For what its worth (and proper names, to unmuddle confusion, can be worth a lot), the above mentioned "curry" function in ANSI Common Lisp is called partial application, that is, you apply a few fixed arguments and return a new function that takes a lower number of arguments, with the first already pre-populated.

Excellent for making lots of custom functions for producing different HTML tags, and that kind of thing. In javascript, libraries often name that function "partial", which saves "curry" for currying.

-----

2 points by Jesin 4594 days ago | link

I wonder how we would deal with this:

  [(foo _ _) baz _]
Does that mean

  (fn (x) ((foo x x) baz x))
or does it mean

  (fn (x) ((fn (y) (fn (z) (foo y z))) baz x))

-----

1 point by cchooper 4594 days ago | link

It would mean the former. I think that's the only sensible way to do it.

-----