29
\$\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).

Improve this question
\$\endgroup\$
15
  • \$\begingroup\$ Related. \$\endgroup\$ Commented Apr 14, 2018 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\$ Commented Apr 14, 2018 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\$ Commented Apr 14, 2018 at 10:39
  • 1
    \$\begingroup\$ This is hard to do in most statically typed languages ... I guess you need type functions for this. \$\endgroup\$ Commented Apr 14, 2018 at 19:47
  • 1
    \$\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\$ Commented Apr 14, 2018 at 21:22

23 Answers 23

Reset to default
12
\$\begingroup\$

JavaScript (ES6), 35 bytes

f=g=>g.length<2?g:a=>f(g.bind(f,a))
Improve this answer
\$\endgroup\$
12
\$\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.

Improve this answer
\$\endgroup\$
1
  • 2
    \$\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\$ Commented Apr 18, 2018 at 3:53
7
\$\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!

Improve this answer
\$\endgroup\$
0
7
\$\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

Improve this answer
\$\endgroup\$
3
  • \$\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\$ Commented May 27, 2018 at 14:56
  • \$\begingroup\$ @ngm The function name must be included when it's recursive. \$\endgroup\$ Commented May 27, 2018 at 18:26
  • \$\begingroup\$ @ngm: I put the if statement inside the sub-function saving a tenth of bytes :) \$\endgroup\$ Commented May 28, 2018 at 16:11
5
\$\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!

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

C++17 20, 214 200 189 184 bytes

#include<regex> template<class R,class A,class...B>auto c(std::function<R(A,B...)>f){if constexpr(sizeof...(B))return[=](A a){return c<R,B...>({std::bind_front(f,a)});};else return f;}

Try it on Wandbox (TIO doesn't support gcc 9+ which is needed for std::bind_front)

This is a template function that takes an std::function of any arity/type and returns a curried lambda expression. Uses constexpr if FTW. If any template gurus have any idea how to eliminate or reduce the need for std::function let me know.

Edit: replaced inner lambda with std::bind_front.
Edit: replaced include with shorter <regex>

Ungolfed version:

#include <functional> template <class R, class A, class... B> auto curry(std::function<R(A, B...)> f) { if constexpr(sizeof...(B) > 0) { return [=](A a) { return curry(std::function<R(B...)>{std::bind_front(f, a)}); }; } else { return f; } }
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat ah of course, good old recursive includes. I'm not sure how standard-compliant that is, but apparently the implicit int-to-bool conversion in a constexpr is already nonstandard (clang rejects it) so as long as gcc doesn't complain I'll take it. \$\endgroup\$ Commented Sep 21, 2020 at 17:25
4
\$\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!

Improve this answer
\$\endgroup\$
0
4
\$\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
Improve this answer
\$\endgroup\$
4
+100
\$\begingroup\$

Rust, 73 69 bytes

macro_rules!c{($f:tt$(($n:tt:$a:ty))*)=>{$(move|$n:$a|)*$f($($n),*)}}

Try it online!

Rust is statically typed and because of this taking in a function with an unknown number of arguments is not allowed. Fortunately, macros have no such restrictions. This macro takes in a function of the form name(arg1:type1)(arg2:type2)...(argN:typeN). and outputs a function that outputs an appropriately long chain of impl FnOnces that ends with the desired function call. I shaved a few bytes by changing the input form to something more natural with the question. Ungolfed version:

macro_rules! c{ //declare a macro named c ( //match on $f:tt //A token tree (should be an ident, but this is codegolf) $( //followed by zero or more sequences of ($n:tt : $a:ty) //a token tree (again, should be ident) colon type in parentheses )* //end repetition )=>{ //replace with $(move|$n:$a|)* //FnOnce closure heads for every matched name:type $f( //call initially matched function $($n),* //with a comma separated list of closure argument names ) //end call } //end rule } //end macro
Improve this answer
\$\endgroup\$
0
3
\$\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!

Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Mmm, Cauliflower curry. Delicious. ^_^ \$\endgroup\$ Commented May 15, 2018 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\$ Commented May 15, 2018 at 5:41
3
\$\begingroup\$

Java 8, 19 + 126 = 145 bytes

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

import java.util.*; 

f->p->new C(){List a=new Stack();public Object f(Object r)throws Throwable{a.add(r);return a.size()<p?this:f.f(a.toArray());}}

Try It Online

Submission type

The submission defines appropriate functional interfaces for the input and output functions. The definitions of the interfaces aren't included in the byte count because they only provide type information and don't contribute any code to the solution. (In fact, both of them are general enough that they could well have been included in the set of functional interfaces in the standard library.) For more details see the TIO.

Usage

Because the submission returns a function (instance of C), the output may be invoked directly (with f), but subsequent intermediate return values must be cast to an appropriate type before being invoked. Consult the TIO for a usage example.

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.f(a1, a2, a3), and rather than f(a1)(a2)(a3) we have f.f(a1).f(a2).f(a3) (modulo typecasting).

Limitations

When an intermediate result is applied (an argument added), the result is actually a mutated copy of the original result. This violates the spirit of currying, but meets the specific requirement stated in the challenge.

The form of input functions is limited by the decision to use functional interfaces, since a fully general functional interface has to use variadics or otherwise pack function parameters, and as a result the implementors of the interface must do so as well rather than listing parameters in the standard fashion. Technically this might disqualify the solution, since it is possible to support fully general non-variadic multi-parameter input functions by invoking them using reflection. My solution using this strategy (taking a java.lang.reflect.Method instead of an instance of a functional interface thanks to @user) is a bit longer, so I stick with this one.

Ungolfed

f -> p -> new C() { List a = new Stack(); public Object f(Object r) throws Throwable { a.add(r); return a.size() < p ? this : f.f(a.toArray()); } }

Acknowledgments

  • -211 bytes thanks to ideas from KrystosTheOverlord
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I love the use of Function<> in your answer! Rather than using reflection though wouldn't it be easier to just use ternary statements and casting? I submitted my own answer doing just that above \$\endgroup\$ Commented Sep 14, 2020 at 19:17
  • \$\begingroup\$ Would it be possible to use a Method as the input instead? \$\endgroup\$ Commented Sep 14, 2020 at 22:31
  • 1
    \$\begingroup\$ @user Good idea. I wrote up a solution using Method and I think it is quite a bit shorter than my original solution. It ends up longer than my latest solution that uses custom functional interfaces and doesn't support writing input functions as lambda expressions, but it does support multi-parameter input functions unlike any functional interface approach. I might add that Method solution here later for completeness. \$\endgroup\$ Commented Sep 16, 2020 at 7:08
2
\$\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!

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

Perl 6, 42 40 bytes

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

Try it online!

-2 bytes thanks to Brad Gilbert b2gills.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You don't need to use a trailing *, it is only necessary if there is something after it like .assuming(*,1). \$\endgroup\$ Commented Apr 14, 2018 at 15:12
2
\$\begingroup\$

Haskell, 211 209 189 163 bytes

Flags:

-XMultiParamTypeClasses -XFlexibleInstances

Actual code (119 bytes):

class C a b c where c::(a->b)->c instance C()b b where c f=f() instance C a b c=>C(d,a)b(d->c)where c a b=c(\d->a(b,d))

Try it online!

The input type of the function to be curried is a nested tuple in a cons-like structure. The uncurried version of a function that adds 3 numbers together would look something like this, where it ends in an empty tuple.

myAdd :: (Int, (Int, (Int, ()) ) ) -> Int myAdd (a, (b, (c, _))) = a + b + c

It works from the bottom up. There's an instance to curry a function of type () -> r that just applies the empty tuple to the function. Then there's another instance of C that can curry a function of type (a,b)->c if there is already an instance of C for b -> c.

Here's an uncurr function to accompany the currying function:

class Uncurry a b c d where uncurr :: (a->b)->c->d instance Uncurry a r (a,()) r where uncurr f (a,()) = f a instance Uncurry a b c d => Uncurry e (a->b) (e,c) d where uncurr f (e,c) =(uncurr(f e) c)

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 5 bytes

Good ol' Mathematica built-ins

Curry

Takes 2 arguments, the function and the number of arguments.

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Julia 1.0, 40 bytes

f>n=n<2 ? f : ((x...)->y->f(x...,y))>n-1

Try it online!

Improve this answer
\$\endgroup\$
1
\$\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

Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Java 8... Using lambda insanity, 152 bytes

Ok so I know that there is already a java 8 answer, but I wanted to use one using almost entirely lambdas without the use of java's Function<> class.

Here is the functional interface for the lambda expressions

interface K{Object f(int...x);}

And here is the actual expression

a->a.length==2?(K)c->a[0]+a[1]*c[0]:a.length==3?a[0]+a[1]*a[2]:(K)b->(b.length == 1)?(K)c->a[0]+b[0]*c[0]:a[0]+b[0]*b[1];

Yeah, so I know this looks really crazy, but the latter is mainly just using ternary operators to distinguish different number of arguments to what needs to be returned.

Given the submitted function

K function = a->a.length==2?(K)c->a[0]+a[1]*c[0]:a.length==3?a[0]+a[1]*a[2]:(K)b->(b.length == 1)?(K)c->a[0]+b[0]*c[0]:a[0]+b[0]*b[1];

function(a, b, c) is function.f(a, b, c), function(a)(b)(c) is ((K)((K)function.f(a)).f(b)).f(c)

Basically any situation that results in a curried result, the answer must be cast to (K) so then it can have a function called on it, otherwise the result is an integer. You can even do the following! (function(a))(a,b) which would be ((K)function.f(a)).f(b,c) etc...

This probably took me way too long, and we already have a java 8 answer, but I feel like it is still an interesting way to go about it.

Improve this answer
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I like the idea of creating a variadic functional interface! I wonder if that would be useful for reducing the length of my solution too. I think I get what you're doing here, but I'm not sure you have a full solution yet. What I see are functions that take int args, not a function that takes a function. It looks like what you've done is curried the example input function from the challenge description rather than implementing a function that itself curries. \$\endgroup\$ Commented Sep 16, 2020 at 0:45
  • \$\begingroup\$ Oh I must've misunderstood, I am still new to functional programming and am fascinated with it. So how would giving it a function as a parameter work then? And where could I find some resources to guide me in the right direction? \$\endgroup\$ Commented Sep 16, 2020 at 1:59
  • \$\begingroup\$ Yeah, no worries! It looks like you're familiar with lambdas and functional interfaces, and those are the main things you'll need. The most helpful resource in this case might actually be my Java 8 answer since it demonstrates a way to write a solution that both takes a function and returns one. Your functional interface K would be a good starting point too, since it's an appropriate type for the input function. \$\endgroup\$ Commented Sep 16, 2020 at 2:13
  • \$\begingroup\$ I'm happy to provide some more help or answer further questions, but probably best to open a chat room for it. \$\endgroup\$ Commented Sep 16, 2020 at 2:16
  • \$\begingroup\$ Alrighty I have made a room -> chat.stackexchange.com/rooms/113053/java-8-functional-currying, I think I get the gist, I'll have to look over your code alot more closely \$\endgroup\$ Commented Sep 16, 2020 at 2:18
1
\$\begingroup\$

Lispy, 169 bytes

(define f(lambda A(begin(define G(lambda(X)(if(>=(length X)C)(proc:apply(head A)X)(lambda Args(G(concat X Args))))))(define C(length(lambda:args(head A))))(G(tail A)))))

Implements the generic abritrary ES5 currying algorithm on Rosetta Code.

Ungolfed and test:

(begin ;; f is a lambda that captures all arguments (define f (lambda Arguments (begin ;; function extraCurry(f) { (define F (head Arguments)) (define A (tail Arguments)) (define _curry (lambda (XS) ;; function _curry(xs) { (if (>= (length XS) intArgs) ;; xs.length >= intArgs ? (proc:apply F XS) ;; f.apply(null, xs) (lambda Args ;; : function() { (_curry (concat XS Args))) ;; return _curry(xs.concat([].slice.apply(arguments))) ) )) (define intArgs (length (lambda:args F))) ;; intArgs = f.length (_curry A) ;; return _curry([].slice.call(arguments, 1)) ))) (define product3 (lambda (a b c) (* a b c))) ;; [14, 28, 42, 56, 70, 84, 98, 112, 126, 140] (print (map [1 2 3 4 5 6 7 8 9 10] (((f product3) 7) 2))))

Try online link coming soon.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Dotty, 345 ... 221 186 bytes

def>[F,T,X](f:F)(using? :F TupledFunction T,e:T=>X)=e(?tupled f) given[A]as((EmptyTuple=>A)=>A)=_(Tuple()) given[A<:Tuple,B,C,D](using t:(A=>B)=>C)as((D*:A=>B)=>D=>C)=f=>h=>t(c=>f(h*:c))

Try it in Scastie

This will not work in Scala 3.0 as TupledFunction will be removed. However, it may be added back later.

This one doesn't do any unsafe casting or other trickery.

> is the method to call. The type parameters F, T, and X represent the type of the input function, the type of the input function if it took a single tuple instead of multiple arguments, and the type of the resulting curried function, respectively. The first parameter, f, is the function to be curried. There are also two implicit parameters, ? and e. ? is a TupledFunction object that can convert between F and T, i.e., tuple and untuple a function. It is provided in the standard library automatically, and makes it easier for e to do its work.

e operates on the tupled form of f. There's a base implicit function that takes an a function EmptyTuple=>A and returns an A by just passing an empty tuple to that function. Another given builds on top of that by deconstructing f into D *: A => B (D is the type of the first parameter of f, A is the type of the rest of the parameters as a tuple, and B is the type of f's result). It uses another implicit function of type (A => B) => C, where C is the curried version of A => B. This second case returns a function taking a D and then applying t to a new function where the D from before is cons-ed to an A before applying f to it.

Dotty, 144 bytes

def a[T](x:Any)=x.asInstanceOf[T] def c[T,R](f:T=>R,n:Int):Any=>Any=h=>a(n match{case 1=>f(a(Tuple1(h)))case _=>c(t=>f(a(h*:a[Tuple](t))),n-1)})

Try it in Scastie

Requires function to be tupled beforehand.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Factor, 6 bytes

ncurry

Try it online!

Builtin.

A non-trivial implementation might be:

[ [ curry ] times ]

Currying is a pretty uncomplicated affair in a concatenative language. :)

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby, 12 bytes

Ruby has a built-in method curry which can be called on a lambda that gives the desired behavior. The below code returns a lambda that calls curry on its argument.

proc &:curry

Attempt This Online!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.