using Programming;

A Blog about some of the intrinsics related to programming and how one can get the best out of various languages.

Getting started with programming and getting absolutely nowhere (Part 13)

Currying (and not the 'Steph' kind)

Lesson 12: How do we become experts?

In this lessson we're going to talk about currying (and I do mean neither the food nor the basketball player), which is one of the most complex topics in F#. The F# designers (shout out to Don Syme, Phillip Carter, and many others) have done a wonderful job of implementing this very difficult and complex idea, and it's important that we, as F# developers, understand how it works.

Currying is the idea that a function can rewrite itself to support having only one parameter. This is hugely important, and I haven't yet clarified this in our adventure, so I want to do so here. My friend Chris asked for this discussion on Twitter, and I feel absolutely obliged to make it happen.

I want to start this chat off with a quick analogy: you're standing at the checkout line in the grocery store, you start putting all your items on the belt, but the person running the register can only scan one item at a time. Since they want to keep things going quickly, they scan your items in the same order you put them on in. This is similar to currying, where the person who is running the register would be the 'main function' you are calling, but due to the ability to only handle one thing at a time, they take one, handle it, then move to the next one. Now part of the way through you decided you want a 'subtotal', they stop taking items, and deliver the result at that moment to you. This is the partial application of functions.

This analogy is what I want to liken to currying, this is a very difficult concept to understand, and the designers and engineers of F# have done a wonderful job making it happen, they really have. I really want you to have a clear understanding of how currying works, and why we do it. F# makes this extremely trivial: we're going to use the example of summing a list of integers with the List.sumBy method, rather than List.sum. We'll use this to demonstrate what exactly happens with currying.

To start, we'll define a sumBy1 function, which takes a (a list), and computes List.sumBy with a map (projection function). This is a simple task, simply pass map to the List.sumBy function, then pass a.

let sumBy1 map a =
    a |> List.sumBy map

Next, we want to 'curry' this function. As I mentioned before, 'currying' is the process of rewriting the function so that it has one parameter, not two. Here, we do this by pushing a to an inner function, and then returning that inner function. We effectively move the a parameter out of the main function, and into an inner function. If you look at the type signature of this, you'll see it's an ('a -> int) -> 'a list -> int, which our previous function was as well. This should help introduce the 'partial application' process I mentioned before, where we can run just one function and get a result of a partial applied function. (Here, we could call sumBy2 with a map, and not an a, and get the 'partially applied' version, we can also do that with the previous version: sumBy1.)

Another good point to discuss here is that signature. The a -> b -> c signature that we're seeing on these functions tells us how F# curried it. Each of the arrows is a new result, it's a return. So a -> b -> c takes an 'a', and returns a b -> c, which is a function. So it takes the first input, then returns a function which can take the second input, and then returns the final result. This should begin to make it clear why we are discussing currying and partial application together: they're directly related.

We can write a pre-curried version of our sumBy1 function, which we'll call sumBy2, and have it posess the same ('a -> int) -> 'a list -> int signature.

let sumBy2 map =
    let inner a =
        a |> List.sumBy map

Here's an interesting observation: we magically created a new variable within our function, we never got passed an a, but we managed to create it out of nowhere. It just appeared. That's how currying works. It doesn't care about the parent function at all, it's concerned about the individual function currently in scope. We can create variables at will, and gather a whole new featureset, we don't have to even worry of the parent function.

Now with this sumBy2, it should be obvious that inner can be rewritten again to eliminate the inner function altogether, and we can make an actual function that is the inner function, as seen below:

let sumBy3Inner map = map |> List.sumBy

What this introduces us to is composition, realistically, we could write let sumFn = sumBy3Inner id, for example, to build the partially applied version of our function. What should be interesting here is that we're piping the map, even though we're not executing the function. We're simply building it up. We could call a |> sumBy3Inner id, but we're going to build a sumBy3 to further compose the chain.

let sumBy3 a = a |> sumBy3Inner

Now we get into some complex currying. We want to write our function such that the arguments are reversed: we take the list first, then the function second. This leaves us with the sumBy4 example, but it's more difficult than that, we need to find a way to curry it out.

let sumBy4 a map =
    a |> List.sumBy map

Curiously, the solution to this is actually the exact same solutions as we did for sumBy2, but instead of inner a, we'll build inner map. The same partial application aspects apply, and we've built a whole new function inside the previous one. The issue here, is that we can't abstract the inner function out, it's just not possible.

let sumBy5 a =
    let inner map =
        a |> List.sumBy map

Now if we collect the sum of each of these functions, we find that each of the results is a single int - this tells me our functions probably work, because we're working with very different types. We can also, of course, run this in F# interactive and prove it to ourselves, which we'll do.

let sum1 = [1..100] |> sumBy1 id
let sum2 = [1..100] |> sumBy2 id
let sum3 = [1..100] |> sumBy3 id
let sum4 = id |> sumBy4 [1..100]
let sum5 = id |> sumBy5 [1..100]

So all five of our values here result in the same thing, an int of the value 5050. This demonstrates that currying has no net effect on the result. The next question you might have is how does this apply to more than two parameters? The same as it applies to just two:

let fnWith3Params a b c =
    a + b + c

let curriedFnWith3Params a =
    let innerFn1 b =
        let innerFn2 c =
            a + b + c

We just recursively apply the currying. The most inner function returns the full result, and each outer function returns it's inner. This is all the magic, which can hardly be classified as magic. Now when we talk about partial application, there's no magic here either. Now that the function is curried, we can pretty cleanly explain partial application.

When we partially apply we don't do anything particularly abstract, we actually do some pretty standard stuff. With our curriedFnWith3Params example, when we let tempFn = curriedFnWith3Params 1, we simply get innerFn1 with the innerFn2 value a pre-applied. When we let tempFn = tempFn 2, we get innerFn2 with a and b pre-applied (or baked-in), then when we call tempFn 3, we get the result of that which is 6. That's it! No magic!

let add1 = 1 + 2 + 3
let add2 = fnWith3Params 1 2 3
let add3 = curriedFnWith3Params 1 2 3

As previously demonstrated, our three-parameter function results are all the same. We've proven that we get the same result, regardless of which form we use to write it, we have also proven that currying can be done, and it can easily be done, and we can even abstract the curried functions out of the main function and reuse them.

By now you should have a basic idea of how this comes in to play with composition. It should be somewhat clear that when we build a composition chain, we're essentially asking the compiler to build a new function that is a very straightforward chain of the others. These can even be curried as well.

At this point, you may be asking yourself: "why is this important, why do I need to understand this?" There's a very long, drawn out and contrived answer to this, so instead, I'm going to be realistic: you probably don't need to know the drawn-out details of currying, but here's what you do need to know:

  • A function has exactly one parameter, so if it looks like it has more than one, it really doesn't. Each parameter produces a new function with exactly one parameter, in the case of multi-parameter functions.
  • When we call one of these functions, we are actually calling into a tree of functions, which means we can stop at any branch and get the current "prepared" chain.
  • A comma-separated list of arguments, and a space-separated (with no comma) list of arguments are different: one builds a set of tupled parameters, the other builds a set of functions.

For a developer coming from C#, C++, VB.NET, PHP, Java, or JavaScript (or any other language where you separate parameters/arguments by commas), this might seem weird, but when you do that in F# it's considered one argument. A function defined let fn (p1, p2, p3) is not the same as a function defined let fn p1 p2 p3: the first function takes a single parameter that has three parts, and the second function is three curried functions each taking a single parameter for it's part.

Interestingly, we can apply the aspect of currying to our own design patterns, instead of needing all the parameters up-front, we can build functions that take some of the parameters and then return a new function to take the rest. This let's us maintain SRP (Single-Responsibility Principle) in F#, but in a totally new fashion. We don't need to take a parameter that's currently useless, we can leave that to the function it's being handled by. We can return a new function, which is natively built-in to the language, so our users don't have any idea that we didn't need the new parameter initially.

I actually demonstrated this the other day, in the example of bad code I wrote. When I have the match p |> getSpecificity with, I return one of two functions. Both of those functions have the same signature, so I could Have just embedded them in the match. Instead, I took advantage of function currying, so the API only has what is needed, and comes up with new parameters on the fly.

Now I could go on explaining away how this works, I really could. I've been working with this for some time now (48 hours, in fact), and I could tell you another 2-3 pages of storytime. Instead, I want to direct you to one of Scott Wlaschin's references, F# For Fun and Profit, particularly the currying section, as well as the partial application section.

I hope this was useful for you, and I hope that even though this was long winded (100+ lines of explanation for 30 lines of code) you still learned something. My first (and only, really) goal with this series is to help guide you to a new path of learning, I want to share what I know with you, with the hopes that one day you'll share what you know with the rest of us.