22
\$\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
  • 1
    \$\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
  • 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\$ – ბიმო Apr 14 '18 at 21:22

17 Answers 17

12
\$\begingroup\$

JavaScript (ES6), 35 bytes

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

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

| improve this answer | |
\$\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!

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

C++17 20, 214 200 189 bytes

#include<functional>
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.

Edited: replaced inner lambda with std::bind_front.

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\$
  • \$\begingroup\$ Suggest #include<regex> instead of #include<functional> \$\endgroup\$ – ceilingcat 15 hours ago
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\$
  • \$\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\$ – KrystosTheOverlord Sep 14 at 19:17
  • \$\begingroup\$ Would it be possible to use a Method as the input instead? \$\endgroup\$ – user Sep 14 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\$ – Jakob Sep 16 at 7:08
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!

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

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\$
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\$
  • \$\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!

| 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\$

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\$
1
\$\begingroup\$

Dotty, 345 327 233 bytes

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

Try it in Scastie

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

Dotty, 219 bytes

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

Try it in Scastie

Requires casting afterwards.

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\$
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

| improve this answer | |
\$\endgroup\$
0
\$\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\$
  • \$\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\$ – Jakob Sep 16 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\$ – KrystosTheOverlord Sep 16 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\$ – Jakob Sep 16 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\$ – Jakob Sep 16 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\$ – KrystosTheOverlord Sep 16 at 2:18

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.