[Haskell-cafe] "first class" tuples?

[Wolfgang Jeltsch]

Am Dienstag, 17. Februar 2009 14:42 schrieb Peter Verswyvelen:
> Tuples in Haskell always have annoyed me a bit since each tuple of
> different dimension is hardcoded

You are not alone with this. Several people have complained about this in the 
past.

> (I guess compilers enforce a maximum dimension on tuples?)

GHC has an internal module which uses a syntactically extended form of data 
declarations to declare different tuple types:

    data (,) a b = (,) a b

    data (,,) a b c = (,,) a b c

    etc.

These declarations can even be found in some Haddock documentation. So at 
least GHC has an upper bound on tuple size although the Haskell Report states 
that there isn’t one. I remember that in an earlier version of this tuple 
module there was a comment in the source code, saying that there can be no 
tuples with more than 37 or so elements since GHC crashes on tuple 
declarations of bigger size. :-D 

> Since a tuple represents a fixed size data structure with different types
> at each coordinate, it feels as it should be possible to have a couple of
> type and data constructors to build a tuple, and to use recursion at the
> type level to have functions operate on tuples of any dimension.

Definitely!

Make , an infix operator. Then even the syntax (,) works without further ado. 
Make , right-associative, for example. Then you can write (a1,...,an) which 
means (a1,(a2,(...,an))). You just need one data declaration:

    data (a,b) = (a,b)

However, this has the problem that it leads to more partially-defined values 
than with today’s tuples. For example, you could have a *triple* (a,_|_).

So maybe we should treat tuple syntax completely as special syntax (as it is 
today) and define our tuple types so that tuples don’t end with the last 
element (as above) but with an explicit empty tuple (like lists end in a 
nil). This would also give use 1-tuples. We would need the unit type () for 
empty tuples. Then we define a cons type which has a strictness annotation:

    data head :# tail = head :# !tail

The strictness annotation ensures that a tuple which is not _|_ has at least 
its complete skeleton defined, i.e., the only undefined (_|_) parts may be 
tuple elements or parts of tuple elements.

> E.g. one could then have a tmap function that takes a tuple of functions and
> a tuple of values and applies the function at coordinate N to the value at
> coordinate N.
>
> Is something like this possible today in Haskell, e.g. using new features
> like type families, GADTs, template haskell, etc? Or do we need dependent
> types for it?

No dependent types, no template Haskell. Only multiparameter classes and 
functional dependencies (or, alternatively, type synonym families):

    class App fun arg result | fun -> arg result, arg result -> fun where

        app :: fun -> arg -> result

    instance App (val -> val') val val' where

        app = ($)

    instance App () () () where

        app () () = ()

    instance (App fun1 arg1 result1, App fun2 arg2 result2) =>
             App (fun1 :# fun2) (arg1 :# arg2) (result1 :# result2) where

        app (fun1 :# fun2) (arg1 :# arg2) = (app fun1 arg1 :# app fun2 arg2)

(All code untested.)

> In C++x0 I believe it is now possible to do so, since they even allow a
> variable number of template arguments, using recursion at compile time (see
> e.g.
> <http://publib.boulder.ibm.com/infocenter/comphelp/v9v111/index.jsp?topic=/com.ibm.xlcpp9.aix.doc/standlib/header_tuple.htm>)

Doesn’t even C++ allow recursion at compile time in some way? The C++ template 
system is Turing-complete.

> Grapefruit has something like first class records, so I guess it should be
> possible (and simpler) to do this for tuples?

By the way, I have taken several ideas from HList for implementing 
grapefruit-records. However, I didn’t use HList itself since it didn’t do 
exactly what I wanted.

For example, it is better to write :& for a cons-like operator instead of 
`HCons`. (This is the point I made in a recent e-mail about people caring too 
little about identifiers.) Of course, you could define an alias for HCons but 
since this wouldn’t be a constructor, you wouldn’t be able to use it in 
pattern matching (see below).

In addition, I’m not sure whether HList allows you to specify a reordering and 
a selection of record fields by pattern matching. Grapefruit does so which I 
consider very important for arrow-based programming. In a line

    output <- arrow -< input,

output can be a record pattern and input a record expression so that the 
output looks similar to the input. This makes arrow statements almost 
symmetric also in the presence of records. The alternative would be to make 
output a single variable and access the record elements via some field 
selection operator. This makes arrow statements less symmetric.

Best wishes,
Wolfgang