Wolfgang Jeltsch g9ks157k at acme.softbase.org
Tue Feb 17 09:36:34 EST 2009

```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

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:

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.

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
```