Curried functions are isomorphic to tupled functions.

This article is part of a series of articles about software design isomorphisms. Nota bene: it's not about Curry–Howard isomorphism. In order to prevent too much confusion, I chose the title Uncurry isomorphism over Curry isomorphism.

The Haskell base library includes two functions called curry and uncurry, and for anyone aware of them, it should be no surprise that they are each others' inverses. This is another important software design isomorphism, because in the previous article, you saw that all methods can be represented in tupled form. The current isomorphism then extends that result because tupled and curried forms are isomorphic.

An F# introduction to curry and uncurry #

While Haskell programmers are likely to be familiar with curry and uncurry, developers more familiar with other languages may not know them well. In this section follows an introduction in F#. Haskellers can skip it if they like.

In F#, you often have to interoperate with code written in C#, and as the previous article explained, all such methods look to F# like functions taking a single tuple as input. Sometimes, however, you'd wish they were curried.

This little function can help with that:

// ('a * 'b -> 'c) -> 'a -> 'b -> 'c
let curry f x y = f (x, y)

You'll probably have to look at it for a while, and perhaps play with it, before it clicks, but it does this: it takes a function (f) that takes a tuple ('a * 'b) as input, and returns a new function that does the same, but instead takes the arguments in curried form: 'a -> 'b -> 'c.

It can be useful in interoperability scenarios. Imagine, as a toy example, that you have to list the powers of two from 0 to 10. You can use Math.Pow, but since it was designed with C# in mind, its argument is a single tuple. curry to the rescue:

> List.map (curry Math.Pow 2.) [0.0..10.0];;
val it : float list =
  [1.0; 2.0; 4.0; 8.0; 16.0; 32.0; 64.0; 128.0; 256.0; 512.0; 1024.0]

While Math.Pow has the type float * float -> float, curry Math.Pow turns it into a function with the type float -> float -> float. Since that function is curried, it can be partially applied with the value 2., which returns a function of the type float -> float. That's a function you can use with List.map.

You'd hardly be surprised that you can also uncurry a function:

// ('a -> 'b -> 'c) -> 'a * 'b -> 'c
let uncurry f (x, y) = f x y

This function takes a curried function f, and returns a new function that does the same, but instead takes a tuple as input.

Pair isomorphism #

Haskell comes with curry and uncurry as part of its standard library. It hardly comes as a surprise that they form an isomorphism. You can demonstrate this with some QuickCheck properties.

If you have a curried function, you should be able to first uncurry it, then curry that function, and that function should be the same as the original function. In order to demonstrate that, I chose the (<>) operator from Data.Semigroup. Recall that Haskell operators are curried functions. This property function demonstrates the round-trip property of uncurry and curry:

semigroup2RoundTrips :: (Semigroup a, Eq a) => a -> a -> Bool
semigroup2RoundTrips x y =
  x <> y == curry (uncurry (<>)) x y

This property states that the result of combining two semigroup values is the same as first uncurrying (<>), and then 'recurry' it. It passes for various Semigroup instances:

testProperty "All round-trips" (semigroup2RoundTrips :: All -> All -> Bool),
testProperty "Any round-trips" (semigroup2RoundTrips :: Any -> Any -> Bool),
testProperty "First round-trips" (semigroup2RoundTrips :: First Int -> First Int -> Bool),
testProperty "Last round-trips" (semigroup2RoundTrips :: Last Int -> Last Int -> Bool),
testProperty "Sum round-trips" (semigroup2RoundTrips :: Sum Int -> Sum Int -> Bool),
testProperty "Product round-trips" (semigroup2RoundTrips :: Product Int -> Product Int -> Bool)

It's not a formal proof that all of these properties pass, but it does demonstrate the isomorphic nature of these two functions. In order to be truly isomorphic, however, you must also be able to start with a tupled function. In order to have a similar tupled function, I defined this:

t2sg :: Semigroup a => (a, a) -> a
t2sg (x, y) = x <> y

The t2 in the name stands for tuple-2, and sg means semigroup. It really only exposes (<>) in tupled form. With it, though, you can write another property that demonstrates that the mapping starting with a tupled form is also an isomorphism:

pairedRoundTrips :: (Semigroup a, Eq a) => a -> a -> Bool
pairedRoundTrips x y =
  t2sg (x, y) == uncurry (curry t2sg) (x, y)

You can create properties for the same instances of Semigroup as the above list for semigroup2RoundTrips, and they all pass as well.

Triplet isomorphism #

curry and uncurry only works for pairs (two-tuples) and functions that take exactly two curried arguments. What if you have a function that takes three curried arguments, or a function that takes a triplet (three-tuple) as an argument?

First of all, while they aren't built-in, you can easily define corresponding mappings for those as well:

curry3 :: ((a, b, c) -> d) -> a -> b -> c -> d
curry3 f x y z = f (x, y, z)

uncurry3 :: (a -> b -> c -> d) -> (a, b, c) -> d
uncurry3 f (x, y, z) = f x y z

These form an isomorphism as well.

More generally, though, you can represent a triplet (a, b, c) as a nested pair: (a, (b, c)). These two representations are also isomorphic, as is (a, b, c, d) with (a, (b, (c, d))). In other words, you can represent any n-tuple as a nested pair, and you already know that a function taking a pair as input is isomorphic to a curried function.

Summary #

From abstract algebra, and particularly its application to a language like Haskell, we have mathematical abstractions over computation - semigroups, for example! In Haskell, these abstractions are often represented in curried form. If we wish to learn about such abstractions, and see if we can use them in object-oriented programming as well, we need to translate the curried representations into something more closely related to object-oriented programming, such as C# or Java.

The present article describes how functions in curried form are equivalent to functions that take a single tuple as argument, and in a previous article, you saw how such functions are isomorphic to C# or Java methods. These equivalences provide a bridge that enables us to take what we've learned about abstract algebra and category theory, and bring them to object-oriented programming.

Next: Object isomorphisms.



Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

Published

Monday, 05 February 2018 07:54:00 UTC

Tags



"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!