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=/co...)
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