Recursive Tuples

Started 2021-04

Haskell does not expose the recursive structure of tuples; for each natural number n (up to a certain limit which happens to be 62), Haskell provides a data type for a tuple of size n¹, but there is nothing that relates a tuple of size n to a tuple of size n-1. I think there’s a potentially neater way to define tuples, and in fact it is already suggested by Haskell’s current notation!

The Definition

Instead of treating (,) as special notation for a tuple data constructor, interpret it as like ordinary Haskell that defines an infix operator ,, analogous to the way (:) defines an infix operator : for constructing lists. The only thing that’s special about the tuple infix operator is that there is a corresponding infix type constructor which uses the same notation (a,b :: A,B given a :: A and b :: B). (If you know about HLists in generic programming, this is like the HList HCons operator, though without the HNil constructor that is part of HLists.)

As with any infix operator it makes sense to define left or right associativity so that brackets are not always needed. It may seem an arbitrary choice between left and right associativity, but actually there are significant differences which will become clear later; for now I’m going to use left-associativity and we’ll think about whether this was the right choice later. With left-associativity now in place, we automatically get an interpretation for ordinary tuple notation of any size e.g.

(a, b, c, d) = (((a, b), c), d) :: (A, B, C, D) 

Note how in this definition of tuples, brackets are not intrinsic to tuple notation, but rather serve the same purpose as they do everywhere else in code – which is to set precedence. (Contrast this with Haskell where (a, b, c, d) is just syntactic sugar that gets translated by the compiler to (,,,) a b c d). The ability to set precedence with brackets is still important within tuples since , is not an associative operator; sometimes we could want to group items into tuples differently as in say ((a, b), (c, d)).

The Advantages

There are a few advantages of defining tuples in this way. Firstly, as we’ve already seen, it ties in nicely with existing Haskell syntax. Secondly, it doesn’t set an arbitrary limit to how large tuples can be. And thirdly, with n-tuples defined in terms of (n-1)-tuples, functions acting on n-tuples can be defined recursively in terms of their analog acting on (n-1)-tuples, which makes some generic programming with tuples much more natural.

curry_n

Take curry_n for example², the function that curries a function on an n-tuple:

curry_n :: ((a1, ..., an) -> b) -> a1 -> ... -> an -> b

With tuples defined as above we get the beautifully simple recursive relationship:

curry_n = curry_n-1 . curry

with the base case:

curry_1 = id -- (so curry_2 is a synonym for curry)

In Template Haskell (a meta-programming extension for Haskell), this can be written as³:

curryN :: Int -> Q Exp
curryN 1 = [| id |]
curryN n = [| $(curryN (n-1)) . curry |]

The same recursive relationship applies for uncurry_n with uncurry as the base case: uncurry_n = uncurry_n-1 . uncurry.⁴

Left-associativity vs Right-associativity

Had we chosen right-associativity for ,, the recursive relationships for curry_n and uncurry_n would have looked a bit more complicated – we would have had curry_n = ((.) curry_n-1) . curry – not terrible but not as nice. This is one of the reasons I think left-associativity is a more natural option.

A more simple reason to choose left-associativity over right-associativity for , is that left-associativity is the default for an infix operator⁵, which is because this is the most natural way to group things when reading from left to right⁶. This is particularly true for , because of it’s left curvature.

You could argue though that a disadvantage of left-associativity is that it is not consistent with lists. List appending is right-associative, and this is for good reason as it makes the first element of the list on the left, and in turn this also fits well with the possibility of infinite lazy lists. Although tuples can’t be infinite, right-associativity would still be needed to be able to define a function first that always returns you the left-most element of any size tuple, and similarly for the other numeric parts. I think it is not the end of the world though to not be able to consistently extract numbered parts numbered from left to right; often tuple parts will be accessed by destructuring rather than numerically, and secondly we can still define functions part_n_i for each n, i (e.g. with Template Haskell), which give the ith part of a tuple when it is considered to be of size n.

On balance I still think left-associativity is the “intended” interpretation for ,, though right-associativity is still a valid choice, and is the approach taken by HLists.

Tuples vs HLists

We’ve acknowledged a link between Tuples and HLists; in fact Tuples and HLists are competing implementations that serve exactly the same purpose, which is to represent a statically typed heterogenous collection of values. The only real difference – aside from the fact that HList’s HCons is right-associative – is that the HList implementation relies on more type-level machinery. (I won’t cover the definition of HLists here but you can think of HLists as like lists but where the list structure is at the type level as well as the value level.) This type-level structure can make some kinds of generic programming easier.

For example, consider defining a generic curryN function on tuples that would work for any tuple size. We can do this using type classes and type-level programming (as opposed to Template Haskell), which I have attempted to do for our tuples in this gist here. The code compiles and also works as expected on concrete functions. However, the type inference is not possible when applied to parametrically polymorphic functions. For example, suppose we apply curryN to the polymorphic function third :: ((x, y), z) -> z. In principle the type should be x -> y -> z -> z, but the compiler cannot infer this type. The problem is that it cannot determine that ((x, y), z) is definitely a tuple of size 3, because it cannot infer whether x is itself a tuple or not.

By contract, generic implementations of curryH and uncurryH for HLists don’t have this problem (see gist here for comparison). This is because with HLists it always makes it explicit which case you are in; you can always match on one of the two cases HCons a b and HNil. This is not possible with tuples, because it does not have constructors that keep you within a structured family of types; rather it just gives you back a general element of Type, and you always need to inspect the type to find out if it’s a tuple or not which can’t be done polymorphic type parameters.

The Conclusion

In conclusion, by treating , as an infix operator like any other in Haskell, we’ve seen how it’s possible to naturally relate tuples of size n to tuples of size n – 1; this definition is both simpler and has the advantage of making some kinds of generic programming with tuples more natural. It is not necessarily a clear improvement though since it requires a potentially arbitrary choice between left and right associativity, and means you can no longer deduce the size of tuples that have polymorphic parameters. This is not so much a problem for styles of generic programming like Template Haskell which create a separate version of the function for each arity, but does present problems in some cases if you want to define a single generic function that works for each arity⁷.