Skip to content

Instantly share code, notes, and snippets.

@AlexandraBeautyman

AlexandraBeautyman/curry.md

Last active September 10, 2019 04:52
Show Gist options
  • Save AlexandraBeautyman/d1e001f79d424320a691fb52f462b4d8 to your computer and use it in GitHub Desktop.
Save AlexandraBeautyman/d1e001f79d424320a691fb52f462b4d8 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
curry.md

Curry

Prompt

Write a function called curry that takes a function as an argument and returns a "curried" version of that function.

But what is a "curried" version of a function?

Currying is the process by which a function of N arguments is implemented as N single-argument functions, such that first of them takes in the first argument and returns a function which takes in the 2nd argument, and so on, until the nth single-argument function finally returns the value of the multi-argument function being implemented.

For example, consider the function below:

const add = (x, y) => x + y

This add function takes in two arguments (x and y) and returns a value, the sum of x and y. A "curried" version of add would instead take in only one argument (x), and it would return a function that would take another argument (y) and then return the sum of x and y.

Here is how curriedAdd would behave:

const addedFive = curriedAdd(5)
addedFive(2) // returns 7
// curriedAdd is a curried version of add. When we fed it one argument, it returned another function, which we called addedFive, here, since we created it by feeding curriedAdd 5. We then fed the function addedFive our second argument, and it returned a value equal to the sum of the two arguments.

const addedOne = curriedAdd(1)
addedOne(10) // returns 11

To produce these results, the curriedAdd function would have to look like this:

const curriedAdd = x => y => x + y

So how do we get there?

Our task is not to write curriedAdd, or the curried version of any particular function. Our task is to write a function that will produce the curried version of any function that gets passed in. Here is some code showing what happens when we pass the add function to the curry function:

const add = (x, y) => x + y
const curriedAdd = curry(add)

// curriedAdd can now take one argument at a time
// in other words, it will now behave like `const add = x => y => x + y`

const firstReturn = curriedAdd(1) // returns the function (y => 1 + y)
const result = firstReturn(2) // returns the value 3

And here is some code showing the same thing for a different function as the original argument, performThisCalc:

function performThisCalc (var1, var2, var3, var4) {
  return var1 + var2 - var3 * var4;
}

const curriedPerform = curry(performThisCalc); // a curried function
const firstReturn = curriedPerform(1); // var1 partially applied
const secondReturn = firstReturn(2); // var2 partially applied
const thirdReturn = secondReturn(3); // var3 partially applied
const finalResult = thirdReturn(4); // -9 -> (1 + 2 - 3 * 4)

Clarifying Details

  • The curried function should still be able to accept multiple arguments at one time. For example, with curriedPerform, we should still be able to say curriedPerform(1, 2, 3, 4) all at once.

  • Curried functions at any stage should be able to be re-used. For example:

function greet (title, name) {
  return "Hello, " + title + " " + name
}

const curriedGreet = curry(greet)

const greetJedi = curriedGreet('Jedi Master')
const greetSithLord = curriedGreet('Darth')

greetJedi('Mace Windu') // "Hello, Jedi Master Mace Windu"
greetSithLord('Vader')  // "Hello, Darth Vader"

  • Reusability applies to the curry function itself, as well. You should be able to feed different functions into it as arguments consecutively and still get the right results.

  • The curry function has to work for input functions that take two arguments, functions that take three arguments, functions that take four arguments, etc. You can't "hardcode" assuming a particular number.

Solution and Explanation

Here is a solution:

const curry = function (fn) {
  function curriedVersion (...args) { // The ...args syntax allows the function to accept any number of arguments.
    if (args.length >= fn.length) { // fn.length refers to the number of parameters in the original uncurried function.
      return fn(...args)
    } else {
      const partiallyAppliedFn = fn.bind(null, ...args) // By using .bind(null, ...args) here, we creating a new version of the original function, the difference being that some arguments are already bound to it, so it only needs to receive the remaining arguments in order to execute.
      return curry(partiallyAppliedFn)
    }
  }
  return curriedVersion
}

In this solution, when you feed a function like add into curry, it will return another function, one that accepts any number of arguments.

When that function (the curried version of the original) is invoked, it checks whether the number of arguments it has received are equal to (or greater than) the number of arguments accepted by the original uncurried function. If so, it will return the original uncurried function invoked with those arguments.

If not, it will create a new function that is a version of the original uncurried function with the arguments it has received so far bound to it. Check out this link for details on the bind method: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Function/bind

This new function, which is a "partially applied" version of the original, is then itself curried. That is, it is passed into the curry function. The result is a curried version of the partially applied version of the original, and that is what is returned from the curried version of the original function. When this returned function is invoked with the next argument(s), it provides a new "fn.length" for comparision with the number of those arguments. If arguments are fed in one at a time, the over time this fn.length value gets smaller and smaller, as new versions of the original function are generated with more and more arguments bound to them.

At any point, if all remaining arguments are fed in (that is, if the number of arguments fed in matches the length property of the current version of the original function), that version of the function is invoked with those remaining arguments, and the result is the final return.

Example

Let's walk through an example. Say our original, uncurried function is greet, a function with two parameters (in other words, it takes two arguments).

function greet (title, name) {
  return "Hello, " + title + " " + name
}

const curriedGreet = curry(greet)

Here, we initially pass the greet function into curry. We get the inner function returned as a result. If we were defining it directly, it would look like this:

function curriedGreet(...args) {
  if (args.length >= greet.length) {
    return greet(...args)
  } else {
    const partiallyAppliedGreet = greet.bind(null, ...args)
    return curry(partiallyAppliedGreet)
  }
}

(By invoking curry with greet, we get returned the equivalent of the above.)

Now that we have our curried function, we can invoke it with our first argument:

const greetJedi = curriedGreet('Jedi Master')

Stepping through curriedGreet, we first compare the number of arguments we fed in (just one) with the length of greet(two). One is less than two, so we move on to the else block. There we define a new function, partiallyAppliedGreet, which has our first argument bound to it. Then we have to invoke curry again with partiallyAppliedGreet as the argument.

const curry = function (fn) { // This time "fn" is the partiallyAppliedGreet
  function curriedVersion (...args) {
    if (args.length >= fn.length) { // fn.length is now one, because partiallyAppliedGreet only needs one argument. (The other                        piece that it needs to return a value is already bound to it.)
      return fn(...args)
    } else {
      const partiallyAppliedFn = fn.bind(null, ...args)
      return curry(partiallyAppliedFn)
    }
  }
  return curriedVersion
}

This time, what we get out of curry is a curried version of partiallyAppliedGreet. It would look like this if we defined it separately instead of generating it with curry:

function curriedPartiallyAppliedGreet(...args) {
  if (args.length >= partiallyAppliedGreet.length) {
    return partiallyAppliedGreet(...args)
  }
  else {
    const partiallyAppliedPartiallyAppliedGreet = partiallyAppliedGreet.bind(null, ...args)
    return curry(partiallyAppliedPartiallyAppliedGreet)
  }
}

(We generate an equivalent function to the one above by calling curry(partiallyAppliedGreet).)

If we then feed curriedPartiallyAppliedGreet another argument, the conditional will be satisfied (partiallyAppliedGreet has a length of one, and args in this case has a length of one), so the function will return partiallyAppliedGreet with that argument.

greetJedi('Luke Skywalker') // This will return 'Hello, Jedi Master Luke Skywalker'.

Additional Notes for Interviewers

  • An important tool that your interviewee will need to leverage is the .length property of a function. You can use .length to get the number of arguments a function receives. They may not know about this, but they may realize that that there might be some way to determine how many parameters a function has.

  • The interviewee will also need to use .bind to partially apply arguments. They may have been using it exclusively to bind the this context, having forgotten that it can also bind arguments. Again, they may be able to come up with the concept, in which case you can direct them to the .bind documentation.

  • Note that when you partially apply arguments with .bind, this returns a new function whose length is decreased based on the number of those arguments! For example:

const takesTwo = (x, y) => x + y
console.log(takesTwo.length) // 2

const takesOne = takesTwo.bind(null, 42) // The number 42 here is arbitrary. The point is, takesOne has whatever value(s) you include after null bound to it. After you bind one value to takesTwo, it's length will be decreased by one.
console.log(takesOne.length) // 1

  • When your interviewee finishes, make sure they check that their curried functions are reusable, and that they can handle more than one argument at a time.

  • What if the function receives more arguments than it has room for? It should just ignore them like any JavaScript function does.

  • Should I handle this context in any particular way? You may assume that any functions passed to curry do not have a special this context that needs to be preserved.

One wrong solution that may come up

When I made an attempt to solve this problem myself, the first thing I came up with was something like this:

function curry(fn) {
  const argsArray = []
  const originalLength = fn.length
  function curriedFn (...args) {
     if (argsArray.length >= fn.length - 1) {
         return fn(...argsArray, ...args)
     }
     else {
         argsArray.push(...args)
         return curriedFn
     }
  }
  return curriedFn
}

This won't cut it, though! The function we return isn't re-usable because it closes over the same array! If your interviewee comes up with this, congratulate them on creating some working logic for dealing with arguments one at a time, but point out that they can't use their function on more than one input function, because they will always be mutating the argsArray.

A fancy one-liner version of the solution, just for fun

const curry = fn =>
  (...args) =>
    args.length >= fn.length ?
      fn(...args) :
      curry(fn.bind(null, ...args))

Summary

Currying is a very common functional programming technique. In fact, in pure functional languages, all functions are curried by default! If your functions are curried, it becomes easy to compose different functionality from the same basic building blocks.

Remember that you can bind the number of arguments (or arity) of a function using .length.

Remember that you can use .bind to partially apply arguments to a function, as well as to preserve its this context.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment