20
\$\begingroup\$

Having a function f that takes arguments x1, x2, …, xn

                                               – ie.  f : X1 × X2 × … × Xn → Y

currying redefines f as a function taking a single argument a1 which maps to yet another function. This technique is useful for partial application, for example with a curried pow function we could write exp = pow(e).

Example

Assuming we have the following function f taking three arguments (f : X1 × X2 × X3 → Y):

def f(a,b,c):
  return a + b * c

Currying this function leaves us with f_curry: X1 → (X2 → (X3 → Y)), if we would now call that function twice with f_curry(1)(2) we would get a function (h) equivalent to the following returned:

def h(c):
   return 1 + 2 * c

The curried function f could be written like this (Python 3):

def f_curry(a):
  def g_curry(b):
    def h(c):
      return a + b * c
    return h
  return g_curry

Try it online!

Challenge

Your challenge will be to curry a function as described above, here are the rules:

  • Input will be a blackbox function which takes at least 2 arguments
  • The input function will always have a fixed number of arguments (unlike printf or similar, note: you need to support functions with any number of arguments ≥2)
  • If your language uses curried functions by default (eg. Haskell), you may expect the input function to be defined over N-tuples, instead of a "higher-order function"
  • You may take the number of arguments as input
  • Output will be the input's curried equivalent*
  • You may assume that the output function will only ever be:
    • called with less or equal to the number of arguments that the input function takes
    • called with arguments of the right type

* This would mean for an input f with N arguments and an output h that for all valid arguments a1,…,aN it holds that f(a1,a2,…,aN) == h(a1)(a2)…(aN).

\$\endgroup\$
  • \$\begingroup\$ Related. \$\endgroup\$ – ბიმო Apr 14 '18 at 10:26
  • \$\begingroup\$ so the input is def f(a,b,c): return a + b * c and the output is def f_curry(a): def g_curry(b): def h(c): return a + b * c return h return g_curry? \$\endgroup\$ – DanielIndie Apr 14 '18 at 10:35
  • \$\begingroup\$ @DanielIndie: If you're taking that example the input would be f (which is defined somewhere) and the output should be something equivalent to f_curry. Or the input would be lambda a,b,c: a+b*c and the output a function equivalent to f_curry. \$\endgroup\$ – ბიმო Apr 14 '18 at 10:39
  • \$\begingroup\$ This is hard to do in most statically typed languages ... I guess you need type functions for this. \$\endgroup\$ – Paŭlo Ebermann Apr 14 '18 at 19:47
  • \$\begingroup\$ @PaŭloEbermann: True, some languages won't be able to solve this task (note the tag functional-programming). However some statically typed languages might be able to use function pointers which would be a valid I/O, that's mainly the reason I allowed taking the number of arguments as additional input. \$\endgroup\$ – ბიმო Apr 14 '18 at 21:22

13 Answers 13

11
\$\begingroup\$

JavaScript (ES6), 35 bytes

f=g=>g.length<2?g:a=>f(g.bind(f,a))
\$\endgroup\$
9
\$\begingroup\$

Idris, 204 bytes

import Data.HVect
C:(a:Vect n Type)->(HVect a->Type)->Type
C[]T=T[]
C(h::t)T=(x:h)->C t(T .(x::))
c:{a:Vect n Type}->{T:HVect a->Type}->((b:HVect a)->T b)->C a T
c{a=[]}f=f[]
c{a=h::t}f=\v=>c(\u=>f(v::u))

Try it online!

Sounds like a job for dependent types! Well, maybe.


C is a currying type function. Given a vector of types a = [t1, t2, … tn] and a type function T : HVect a → Type, it returns a new type:

           (x1 : t1) → (x2 : t2) → … → (T [x1, x2, … xn])

Here, HVect is the heterogeneous vector type from the Idris Prelude — the type of n-tuples whose elements are of n different types.

c is a function that takes a and T as implicit arguments, and then converts an uncurried function f of type ((b : HVect a) → T b) into a curried one of type C a T.

(C simply describes what we wish to do; c actually does it. But we can't get away with not defining C, as Idris demands that every top-level definition have a type signature.)


The TIO link gives a usage example. If we define a function on 3-tuples (Nat, Nat, String) as follows:

uncurried : HVect [Nat, Nat, String] -> String
uncurried [a, b, c] = show (a*a + b*b) ++ c

then uncurried [3, 4, "th"] yields the same result as c uncurried 3 4 "th". Idris infers the arguments a=[Nat, Nat, String] and T=const String for us, I believe.

I based this code on this gist by timjb.

\$\endgroup\$
  • \$\begingroup\$ In my opinion, tuples in Haskell and Idris should actually be HVect by default—HVect is essentially a tuple that you can uncons. \$\endgroup\$ – Esolanging Fruit Apr 18 '18 at 3:53
5
\$\begingroup\$

Python 3, 54 53 bytes

c=lambda n,f,*x:lambda y:(f,c)[n>1](*1%n*(n-1,f)+x,y)

Try it online!

\$\endgroup\$
5
\$\begingroup\$

R, 96 bytes

y=function(f,n=length(formals(f)),p=list())function(x,u=c(p,x))`if`(n<2,do.call(f,u),y(f,n-1,u))

Try it online!


Previous version (97 bytes)

-1 byte thanks to @JayCE

\$\endgroup\$
  • \$\begingroup\$ I don't see how to fundamentally shorten it. You can golf away three bytes by getting rid of the braces and the space at the end of the first line. And two more due to the convention here of not including the name of the function in the byte count. TIO \$\endgroup\$ – ngm May 27 '18 at 14:56
  • \$\begingroup\$ @ngm The function name must be included when it's recursive. \$\endgroup\$ – Ørjan Johansen May 27 '18 at 18:26
  • \$\begingroup\$ @ngm: I put the if statement inside the sub-function saving a tenth of bytes :) \$\endgroup\$ – digEmAll May 28 '18 at 16:11
4
\$\begingroup\$

Coconut, 54 bytes

def c(f,*a):
 try:return f(*a)
 except:return c$(f,*a)

Try it online!


Coconut, 40 bytes

Port of Erik's Python answer.

def c(f,n,*a)=n and c$(f,n-1,*a)or f(*a)

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python 2, 60 bytes

c=lambda f,n,l=[]:lambda a:n-1and c(f,n-1,l+[a])or f(*l+[a])

Try it online!

The footer is a tester which uses STDIN in the following way per line:

  1. The function itself
  2. The number of the function's arguments, ≥2
  3. A list of the arguments ([a,b,...])

Note that, while a list of the arguments is given as input in the tester, in reality, the curried equivalent gets prepended to the list and the list is reduced by function call.

A similar 55-byte version has been kindly provided by ovs:

c=lambda f,n,*l:lambda a:n-1and c(f,n-1,*l,a)or f(*l,a)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Cauliflower, 84 bytes

(:= c(\($f$n(@a))(if$n(\($a)(call c(cat(list$f(-$n 1))@a(list$a))))else(call$f@a))))

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Mmm, Cauliflower curry. Delicious. ^_^ \$\endgroup\$ – DLosc May 15 '18 at 3:00
  • \$\begingroup\$ @DLosc there aren't enough answers to this challenge in langauges with food-related names :P (although I guess most of them don't actually have functions) \$\endgroup\$ – ASCII-only May 15 '18 at 5:41
2
\$\begingroup\$

Perl 6, 42 40 bytes

my&c={.count>1??{c(.assuming($^a))}!!$_}

Try it online!

-2 bytes thanks to Brad Gilbert b2gills.

\$\endgroup\$
  • \$\begingroup\$ You don't need to use a trailing *, it is only necessary if there is something after it like .assuming(*,1). \$\endgroup\$ – Brad Gilbert b2gills Apr 14 '18 at 15:12
1
\$\begingroup\$

Python 2, 78 bytes

c=lambda f,*a:f.func_code.co_argcount>len(a)and(lambda x:c(f,*a+(x,)))or f(*a)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Attache, 5 bytes

Curry

Try it online!

Simple built in, largely uninteresting. But, here's a version from scratch:

Attache, 35 bytes

{If[#__2<#_,Fold[`&:,$'__],_@@__2]}

Explanation:

{If[#__2<#_,Fold[`&:,$'__],_@@__2]}
{                                 }    lambda
 If[       ,              ,      ]     if
    #__2                                 the number of parameters after the first
        <#_                              is less than the arity of the first
            Fold[   ,    ]             then fold:
                 `&:                     right-function bonding
                     $                     over this function
                      '__                  paired with the rest of the parameters
                          ,            otherwise:
                           _@@           call the first parameter
                              __2        with the rest of them
\$\endgroup\$
1
\$\begingroup\$

Java 8, 46 + 318 = 364 bytes

This is a curried (hah) lambda taking a function and an argument count and returning the curried function.

import java.lang.reflect.*;import java.util.*;

f->p->new java.util.function.Function(){Object F=f;Method m=F.getClass().getDeclaredMethods()[0];int P=p;List a=new Stack();public Object apply(Object r){a.add(r);try{return a.size()<P?this:m.invoke(F,a.toArray());}catch(Throwable t){t=t.getCause();if(t instanceof Error)throw(Error)t;else throw(RuntimeException)t;}}}

Try It Online

Submission type

Input function

The function input is an object with a single method (excluding inherited methods) representing the function. Note that a standard functional interface cannot be used as the input type because functions of (e.g.) 3 parameters must be supported. Also note that a lambda expression cast to a standard java.util.function.Function-like type may be passed (the single method is apply).

Checked exceptions may be declared on the input function, but they may not be thrown (i.e. they will not be propagated to the caller of the output function). This is presumed to be acceptable because Java's functional interfaces do not permit checked exceptions (and propagating them would prevent the submission from returning a Function). Runtime exceptions (assignable to RuntimeException or Error) are propagated.

Output function

The output of the submission is a java.util.function.Function<Object, Object>. I considered returning a plain Object with an apply method (like in the input), but then reflection would be required to invoke the result, which seemed inconvenient enough to be disallowable—in particular, calling all the way down would no longer be possible in a single expression.

Usage

Because the submission returns a function from Object to Object, the output may be invoked directly (with apply), but subsequent intermediate return values must be cast to an appropriate type (e.g. java.util.function.Function<Object, Object>) before being invoked. Consult the TIO for some usage examples.

Note that in Java functions (i.e. methods) are not first-class objects. Thus the syntax used in the output bullet of the challenge description is meaningless in Java. Rather than f(a1, a2, a3) we have f.apply(a1, a2, a3), and rather than f(a1)(a2)(a3) we have f.apply(a1).apply(a2).apply(a3).

Limitations

When an intermediate result is applied (an argument added), the result is actually a mutated copy of the original result. For example, in this snippet:

Function<Object, Function<Integer, Function>> submission = ...;
Function c = submission.apply((IntBinaryOperator) (a, b) -> a + b).apply(2);
Function c2 = (Function) c.apply(2);
System.out.println(c2.apply(2));
System.out.println(c2.apply(3));

line 4 would print 4, but line 5 would fail, because by that time c2 already holds arguments 2 and 2 (note too that c2 == c). This violates the spirit of currying, but meets the specific requirement stated in the challenge.

Ungolfed

See the TIO for an ungolfed copy.

\$\endgroup\$
1
\$\begingroup\$

Julia 0.6, 48 bytes

c=(f,n,a=[])->n>1?x->c(f,n-1,[a;x]):x->f(a...,x)

Try it online!

Port of @EricTheOutgolfer's Python answer.

\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Classic), 58 57 bytes

∇r←(a f g)x
:If a[1]=≢a
r←g 1↓a,x
:Else
r←(a,x)f g
:End
∇

Try it online!

Calling syntax (with curried function g, arguments x1 through x3, and number of arguments n):

((n x1 f g) x2) x3

Requires ⎕IO←1

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.