peterv wrote:

Hi,

I have a couple of questions about tuples.

Q1) Is it possible to treat a tuple of N elements in a generic way? So instead of writing functions like lift1 e1, lift2 (e1,e2), lift3 (e1,e2,e3) just one function liftN that works on tuples of any length?

If you have instances of Data across the board, you should be able to do this with gmap, gfoldl, etc. (See Data.Generics). Short of that, you'd have a hard time writing the type of liftN.

Q2) (Maybe related to Q1) Can I convert a tuple of length N to a heterogeneous list (using "forall" aka existentially quantified types) and vice versa?

Use Data.Dynamic.Dynamic instead of explicit existentially quantified types, and it should come from gfoldl pretty readily. <snip> Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs

I'm beginning to see that my old implementation in C++ clutters my Haskell design. You see, in C++ I can write: // A vector is an array of fixed-length N and elements of type T template struct Vector { T Element[N]; friend T dot(const Vector& a, const Vector& b) { T result = 0; for( int i=0; i class. I don't think Haskell has something like a "fixed-length array" or constant expressions that *must* be resolved at compile-time (like the N in the C++ template)? Or like Digital Mars D's "static if" statement (which is a control-flow statement that *must* succeed at compile time)? Tuples allow a different type for each element (they are more like "anonymous structs"), so are not really suitable for what I want to do. Now in C++ when implementing this (together with fixed-size matrices), you can get a lot of overhead because the code needs to compute many intermediate results; it has a hard time to unroll all the loops (although I think the latest compilers are much better). Now when implementing something like this in Haskell, I would guess that its laziness would allow to "interleave" many of the math operations, reordering them to be as optimal as possible, removing many intermediate results (like processing streams). So you would automatically get something like the C++ Expression Templates http://ubiety.uwaterloo.ca/~tveldhui/papers/Expression-Templates/exprtmpl.ht ml... Well at least I hope so :) -----Original Message----- From: haskell-cafe-bounces@haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Lukas Mai Sent: Friday, July 13, 2007 09:20 To: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Newbie question about tuples Am Donnerstag, 12. Juli 2007 20:14 schrieb Andrew Coppin:

The only thing the libraries provide, as far as I can tell, is the fact that tuples are all Functors. (In other words, you can apply some function to all the elements to get a new tuple.) I think that's about it. I doubt you can use that to define lifting functions...

Actually, they aren't (Functors). (,) takes two type arguments, (,,) takes three, etc. class Functor f requires f to take one type argument. So something like instance Functor (,) where ... won't compile. Besides, what should fmap (+1) (3, 4, "foo") do? (Somewhere in the libraries there is an instance Functor (,) a where fmap f (x, y) = (x, f y) but that's probably not what you expected.) HTH, Lukas _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe No virus found in this incoming message. Checked by AVG Free Edition. Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007 16:08 No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007 16:08

with guaranteed termination, of course

Just out of curiosity (not Haskell related): I always get confused when people speak about "guaranteed termination"; what about the halting problem? In which context can one check for "guaranteed termination", as the halting problem says it's not *generally* possible? -----Original Message----- From: haskell-cafe-bounces@haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Jonathan Cast Sent: Friday, July 13, 2007 16:21 To: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Newbie question about tuples On Friday 13 July 2007, peterv wrote:

I'm beginning to see that my old implementation in C++ clutters my Haskell design.

You see, in C++ I can write:

// A vector is an array of fixed-length N and elements of type T template struct Vector { T Element[N];

friend T dot(const Vector& a, const Vector& b) { T result = 0; for( int i=0; i

So basically a wrapper around a fixed-size array of any length. Implementations of (+), (-), dot, length, normalize, etc... then work on vectors of any size, without the overhead of storing the size, and with compile-time checking that only vectors of the same size can be used, etc... This also fits in nicely when creating a Matrix class.

I don't think Haskell has something like a "fixed-length array" or constant expressions that *must* be resolved at compile-time (like the N in the C++ template)?

I'm surprised no one has posted anything on type-level programming yet. You might google for that. And GHC 6.8 will have true type-level functions (with guaranteed termination, of course) which will help. But I'm sure a good google will turn up a clearer explanation than I can provide; I've never needed or wanted to understand the type-level stuff. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe No virus found in this incoming message. Checked by AVG Free Edition. Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007 16:08 No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007 16:08

peterv wrote:

...

with guaranteed termination, of course

Just out of curiosity (not Haskell related): I always get confused when people speak about "guaranteed termination"; what about the halting problem? In which context can one check for "guaranteed termination", as the halting problem says it's not *generally* possible?

Presumably by limiting what you're allowed to do in such a way that it will always terminate... nothing more, nothing less.

Super. This is really a great mailing list :) -----Original Message----- From: haskell-cafe-bounces@haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Chung-chieh Shan Sent: Friday, July 13, 2007 16:54 To: haskell-cafe@haskell.org Subject: [Haskell-cafe] Re: Newbie question about tuples peterv wrote in article <013301c7c54e$25232650$6f6972f0$@be> in gmane.comp.lang.haskell.cafe:

I don't think Haskell has something like a "fixed-length array" or constant expressions that *must* be resolved at compile-time (like the N in the C++ template)? Or like Digital Mars D's "static if" statement (which is a control-flow statement that *must* succeed at compile time)?

Actually, Haskell can do it one better: you can have fixed-length arrays whose length is known only at run time. That is, you can have the compiler check that you will only be adding arrays with the same length, but find out what that length is (and pass it around non-redundantly) at run time. (You can encode the same idea, more verbosely, using generics in Java and C#.) Please see (among other work): http://ofb.net/~frederik/vectro/ http://www.cs.rutgers.edu/~ccshan/prepose/ http://www.eecs.usma.edu/webs/people/okasaki/icfp99.ps -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig http://www.unaids.org/en/HIV_data/epi2006/ UNAIDS/WHO AIDS Epidemic Update: December 2006 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe No virus found in this incoming message. Checked by AVG Free Edition. Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007 16:08 No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007 16:08

Yes but doesn't GHC have a good "strictness analyzer" (or how is this called?)? I haven't looked at the generated assembly code yet (if this is at all readable; but good C/C++ compilers *do* generate reasonably readable assembly code) -----Original Message----- From: Bulat Ziganshin [mailto:bulat.ziganshin@gmail.com] Sent: Friday, July 13, 2007 6:43 PM To: peterv Cc: 'Lukas Mai'; haskell-cafe@haskell.org Subject: Re[2]: [Haskell-cafe] Newbie question about tuples Hello peterv, Friday, July 13, 2007, 5:03:00 PM, you wrote:

think the latest compilers are much better). Now when implementing something like this in Haskell, I would guess that its laziness would allow to "interleave" many of the math operations, reordering them to be as optimal as possible, removing many intermediate results (like processing streams).

don't forget that laziness by itself makes programs an orders of magnitude slower :) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

bulat.ziganshin:

Hello peterv,

Friday, July 13, 2007, 5:03:00 PM, you wrote:

...

think the latest compilers are much better). Now when implementing something like this in Haskell, I would guess that its laziness would allow to "interleave" many of the math operations, reordering them to be as optimal as possible, removing many intermediate results (like processing streams).

don't forget that laziness by itself makes programs an orders of magnitude slower :)

Or orders of magnitude faster, depending on your data structure. :) -- Don

Am Freitag, 13. Juli 2007 15:03 schrieb peterv:

You see, in C++ I can write:

[snip]

So basically a wrapper around a fixed-size array of any length. Implementations of (+), (-), dot, length, normalize, etc... then work on vectors of any size, without the overhead of storing the size, and with compile-time checking that only vectors of the same size can be used, etc... This also fits in nicely when creating a Matrix class.

I don't think Haskell has something like a "fixed-length array" or constant expressions that *must* be resolved at compile-time (like the N in the C++ template)? Or like Digital Mars D's "static if" statement (which is a control-flow statement that *must* succeed at compile time)?

You may be interested in http://okmij.org/ftp/Haskell/number-parameterized-types.html http://okmij.org/ftp/Haskell/types.html#branding HTH, Lukas

Lukas Mai wrote:

Am Donnerstag, 12. Juli 2007 20:14 schrieb Andrew Coppin:

...

The only thing the libraries provide, as far as I can tell, is the fact that tuples are all Functors. (In other words, you can apply some function to all the elements to get a new tuple.) I think that's about it. I doubt you can use that to define lifting functions...

Actually, they aren't (Functors).

Oh. Kay... well that makes me look *very* intelligent. :-}

(,) takes two type arguments, (,,) takes three, etc. class Functor f requires f to take one type argument.

Ah. A kind error. Yes, you're right about that... oops.

Besides, what should fmap (+1) (3, 4, "foo") do?

I was assuming it's only defined for (a,a), not for (a,b)...

(Somewhere in the libraries there is an instance Functor (,) a where fmap f (x, y) = (x, f y) but that's probably not what you expected.)

Indeed. Oh well...

On 2007-07-13, Jules Bean wrote:

Andrew Coppin wrote:

...

Lukas Mai wrote:

...

Am Donnerstag, 12. Juli 2007 20:14 schrieb Andrew Coppin:

...

The only thing the libraries provide, as far as I can tell, is the fact that tuples are all Functors. (In other words, you can apply some function to all the elements to get a new tuple.) I think that's about it. I doubt you can use that to define lifting functions...

Actually, they aren't (Functors).

Oh. Kay... well that makes me look *very* intelligent. :-}

...

(,) takes two type arguments, (,,) takes three, etc. class Functor f requires f to take one type argument.

Ah. A kind error. Yes, you're right about that... oops.

nah, you do yourself an injustice, Andrew.

(a,b) is certainly functorial, in both a, and in b. I.e. (,b) is a functor "in the a component", and so is (a,) "in the b component".

Furthermore (a,a) is also functorial: it's just "lists of exactly length two" and we know lists are functorial.

It is a deficiency of the haskell class system (although I'm not trying to claim it's a particularly important one in practice) that it's not really possible to express all these things at once.

It's a deficiency of all OO systems as well. Nothing handles well the case of a structure being usable as a certain type of object two different ways. It's most recognized there as the "multiple inheritance problem", where the same interface (or base class) is inherited twice from different paths, but the problem is deeper than that. -- Aaron Denney -><-