What is currying?

From [Wikipedia] 1

In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument. Currying is related to, but not the same as partial application.

Why curry?

As the definition says, it gives us the ability to invoke functions with a partial set of arguments(in required order) and evaluate the function only after all arguments for the function are available. Therefore,

1. We could re-define functions by providing partial arguments
2. Lazy evaluation - apply arguments to a function, but postpone the final evaluation until it is needed

You are probably familiar with the partial function available in the functools library. partial function can be used to implement currying. But, this can require a lot of boiler plate code, This post walks through the code examples based on the implementation of curry and related classes in [PyMonad] 2. Examples are also adapted from the documentation. The purpose of this post is to walk through the implementation piecemeal and appreciate the power of currying. We will see how just by ‘currying’ and defining certain mapping of functions we can build powerful structures of computation in Python.

Simple advantages - Lazy construction and evaluation

Say, we want to curry a function just by using a decorator called curry. One way would be like,

    @curry
    def add(x, y):
        return x + y

    add(10)(32)
    > 42

    # apply arguments one and a time
    f = add(10)
    f = add(32)
    > 32

In the above example, notice that we could invoke add twice, once for each argument. Once all the arguments to the function have been provided, the function is invoked and the result is available.

How would we implement the curry decorator. Conceptually, here are the things we will have to take care of

1. Recursively apply the arguments to the function as they become available
2. Invoke the function once all argument to the function has been provided

Let’s work on each of these steps. For recursively applying arguments, we need to apply arguments that become available, but also return a callable that can be invoked during the next call. Therefore, we can implement a function we will call a [buildReader] 3

    def buildReader(argValues, numArgs):
        if numArgs == 0:
            return f(*argValues)
        else:
            l =  lambda x: buildReader(argValues + [x], numArgs - 1)
            return l

Here the buildReader recursively invokes itself, applying one argument at a time, but returns a callable that will accept the next argument. Once, all the arguments to the wrapped function is exhausted, the wrapped function in invoked and the final value is returned.

For example, if we were to invoke,

@curry
def add3(x, y, z):
    return x + y + z

then we have a invocation structure for add(10)(20)(30) looks like

(lambda x : builderReader([10] + [x], 2)   # add(10)
(lambda x: builderReader([20, 10] + [x], 1) # add(20)
 60 # add(30)

Now, we still need to handle the base invocation scenario(call made when the decorator is evaluated) and also ability to call the add method repeatedly. Therefore, it would be reasonable to wrap the buildReader in a callable so that this object can be invoked repeatedly. Here, is the updated buildReader along with the callable class.

def curry(f):
    '''
    Custom curry function. Does not handle kw-only args
    '''
    numArgs = f.__code__.co_argcount
    def buildReader(argValues, numArgs):
        if numArgs == 0:
            return f(*argValues)
        else:
            l =  lambda x: buildReader(argValues + [x], numArgs - 1)
            return l
    return CallableClass(buildReader([], numArgs))

class CallableClass:
    '''
    Wrap the function to call inside a callable
    '''
    def __init__(self, func):
        '''

        '''
        self.func = func

    def __call__(self, *args):
        f = self.func
        for a in args:
            # here we are just invoking the buildReader iteratively
            # no error handling to check excess no of arguments
            f = f(a)

        if callable(f):
            # we have not exhausted the argument yet,
            # therefore, continue wrapping the buildReader inside
            # the callable class
            return CallableClass(f)
        return f  # we have the final value after evaluation

Notice, in the above snippet, the __call__ function repeatedly applies the iterable of arguments to the wrapped function, giving us this progression

(lambda x : builderReader([10] + [x], 2)   # add(10)
(lambda x: builderReader([20, 10] + [x], 1) # add(20)
 60 # add(30)

We see that we have achieved our initial objective of being able to use the curry decorator in place of the partial function. We use curried functions as expressions and we can pass them around till they are evaluated.

Simple Composition

In the first step, we were able to create an expression out of one function. We can extend this a little further and create expressions of composed curried functions. For example, say we had

@curry
def add(x, y):
    return x + y

@curry
def mult(x, y):
    return x * y

Then, we would like to declare statements such as

    x = ((add(5) * mult(3))(2))   # '*' is composition operator
    x == (mult(3, add(5, 2)))  # here we compose add and mult
    x == 21

To do this, we just extend out CallableClass to perform * (composition)

    def __mul__(self, func):
        '''
        func: is the outer function in the function composition
        in a * b, func will be a

        Here we need to invoke a first and then invoke b.

        By this point the function operands have all but one argument
        applied to them
        '''

        return CallableClass(lambda x: func(self.func(x)))

Awesome! Now, we can create expressions that are composed functions (that are not yet evaluated). The composed functions can also be declared across multiple statements and then assembled together.

    x = ((add(5) * mult(3))(2))
    y = add(10)
    y = y(x)
    print(y)   # 31

Pipe-lining operations with one common input

Say, we want to compose a series of functions. In addition, we want all the functions in the series to have access to the initial input. For example, say we want

    initial_input = 10
    mult(add(10, initial_input), initial_input)

Here we are sequencing our operations with a predecessor output in addition to the initial value. Lets extend the CallableClass to handle this operation. We will use the rshift operator to support this operation.

    def __rshift__(self, func):
        ''' Compose functions, but also call the inner function
        ''' with x
        return CallableClass(lambda x: func(self.func(x))(x))

Now, we can do the following

    x = (add(10) >> mult())
    print(x(10))  # print 200

We just created an expression that can compose a sequence of methods, in addition to maintaining access to the initial input invoking the expression. Lets, take a look at an nested example

    y = (lambda x: mult(x) >> add())
    x = (add(10) >> y >> mult())
    print(x(10)) # 2100

How the above example works in left as an exercise. But, the important thing to note is that we were able to embed sequence of expressions.

Wrap Up: We just built a Reader Monad

The concept of sequencing a set of methods into a composable functions is abstracted away using concepts called Monad. More precisely, what we just saw was an loose example of a Reader Monad.¹. The [Reader] 5 here provides the full implementation of the Reader Monad. The curious reader, may also want to explore the amap method in this class. This method in turns implements what is called an Applicative.

If you got this far, I suggest you check out [PyMonad] 6

1 I call it loose, since our CallableClass needs to implement a few more methods before it can be called a Monad. But conceptually, we have a Reader Monad at hand. ↩︎