Explaining a currying implementation in Haskell

If you don't feel fluent in functional types in Haskell, it is usually easier to write some redundant parentheses:

curry :: ((a, b) -> c)) -> (a -> (b -> c))
uncurry :: (a -> (b -> c)) -> ((a, b) -> c)

And now we can prove derive the definitions from the types. (don't mind the type variable scoping):

curry = \(f :: (a, b) -> c) -> r1 where -- we have `(a, b) -> c`, but want `a -> (b -> c)`
  r1 :: (a -> (b -> c))
  r1 = \(x :: a) -> r2 where -- we have `a` but want `b -> c`
    r2 :: b -> c
    r2 = \(y :: b) -> r3 where -- we have `b` but want `c`
      r3 :: c
      r3 = f (x, y)  -- we have `c`, because `(x, y) :: (a, b)`, so `f (x, y) :: c`

After unfolding r? variables we get the following definition of curry:

curry = \f -> (\a -> (\b -> f (a, b)))

Which is equivalent in this case to

curry f a b = f (a, b)

This should work similarly with uncurry

We can start one variable at a time:

curry f a b = f (a, b)

a and b are unrestricted values (apart from being arguments to the f function), which means we can give them types, let's say a and b (very creative naming, I know).

So, the current signature is looking like (abusing notation):

curry :: (type of f) -> a -> b -> (type of f (a, b))

Since f is called on (a, b) on the right hand side, we can assume that it's a function that takes a tuple (a, b) and returns some value, let's say c. So, f is (a, b) -> c, so f (a, b) is one level applied, or just c. So, the signature of the function is:

curry :: ((a, b) -> c) -> a -> b -> c

Now, we can try to make sense of this signature. I find it easier to understand when parenthesized as this equivalent expression:

curry :: ((a, b) -> c) -> (a -> b -> c)

You pass in a function that takes a tuple and returns a value, and curry returns a function that takes in two values and returns a value. Essentially, you're unpacking the arguments: going from a function that takes in a single tuple containing 2 values, to a function that takes in the 2 values.

Looking at this in the context of curry fst, fst is \(a, b) -> a. So, curry would unpack the arguments, making it \a b -> a. This is basically the definition of const, returning the first argument and ignoring the second.

Now we can look at uncurry. Using the same reasoning as before, we can say that the argument a has type a, and the argument b has type b, and since f is called on a then b, it must have some type a -> b -> c. So, the type signature looks like:

uncurry :: (a -> b -> c) -> (a, b) -> c

Or, parenthesized as before:

uncurry :: (a -> b -> c) -> ((a, b) -> c)

As the name suggests, this is the opposite of curry. It takes in a function that already takes in 2 arguments, then returns a function that takes in a tuple with the two arguments. Looking at uncurry in a usecase:

λ> f = uncurry (+)
λ> :t f
f :: Num c => (c, c) -> c
λ> f (1, 2)
3
λ> (+) 1 2
3

Also, curry (uncurry f) should be f, for any f that takes in two or more arguments.

Note that curry could also be written

curry f = \a -> \b -> f (a, b)

Because curry itself is curried, it only takes one argument, the function of type (t1, t2) -> t. The definition curry f a b = ... itself is in some sense syntactic sugar for this explicitly defined lambda expression.

Perhaps this is too obvious to point out, but for many Haskell functions that operate on other functions, it's easiest to understand them (or indeed, construct them) by taking the definitions as straightforward equivalencies or rewrite rules, rather than trying to work out how they're typed or how they "operate internally".

For example, if I have an uncurry function defined by:

uncurry f (a, b) = f a b

and want to understand how it works, just take an example of a curried function:

times a b = a * b

and apply uncurry to to it:

uncurry times

The definition above implies that this resulting expression can be applied to a pair and rewritten:

(uncurry times) (4, 8) = times 4 8

From this, it should be abundantly clear how given any curried function f that applies to two curried arguments, the expression uncurry f will produce an uncurried version that applies instead to a pair. What could be simpler? There's nothing left to "understand".

What if I want to implement a function instead of understand a given implementation? For example, if I have an uncurried function, like add (a,b) = a + b, suppose I want to curry it. Well, if I had the curry function to do so:

curry add

then how would it need to behave? The function curry add would take two arguments in curried fashion:

(curry add) a b

and it's result would be the application of the uncurried add to a tuple holding those arguments:

(curry add) a b = add (a,b)

If I generalize this:

(curry f) a b = f (a,b)

I get exactly the top-level declaration that defines curry. You can use it as-is, and it will compile, though it's more usual to drop the redundant parentheses on the left.

This is a helpful way of writing implementations of other high-level functions without much thought. How should the compose operator . be defined? Well, if I composed two functions f . g, its application to an argument ought to be the composition:

(f . g) x = f (g x)

This is a perfectly valid top-level definition of .. For performance reasons (i.e., it affects inlining), it's actually implemented in Prelude as:

(.) f g = \x -> f (g x)

but the above rewrite-based definition still works.

Other (sometimes apparently complicated) high-level functions have equally straightforward rewrite-based definitions, though it's sometimes hard to spot what's being defined:

flip f x y = f y x
x & f = f x

-- define "on" from Data.Function, which applies a binary operation
-- to f-transformed arguments
(binop `on` f) x y = binop (f x) (f y)