[Haskell-cafe] Re: Implementing fixed-sized vectors (using datatype algebra?)

[Wolfgang Jeltsch]

Am Freitag, 1. Februar 2008 13:00 schrieb Alfonso Acosta:
> On Jan 31, 2008 11:35 PM, Wolfgang Jeltsch <g9ks157k at acme.softbase.org> 
wrote:
> > Am Donnerstag, 31. Januar 2008 18:30 schrieb Dominic Steinitz:
> > > Look at
> > >
> > > http://sneezy.cs.nott.ac.uk/fun/feb-07/jeremy-slides.pdf
> >
> > This is essentially what I had in mind.  While Oleg's implementation
> > needs a "thrusted core", the GADT solution doesn't.
>
> True. However using GADTs doesn't allow to internally make use of
> Arrays, which (tell me if I'm wrong) are likely to be faster than the
> naive GADT implementation.

It depends.  My first GADT implementation is equivalent to the [] type and 
often [] is better than arrays.  For example, if you read the contents of a 
file and process it with maps, filters, etc., [] is likely to give you 
constant space usage which arrays don’t.  If you want to lookup elements by 
index, then arrays are better, of course.  For my purpose, it would be fine 
to use a []-like implementation, I think.

> […]

> > Some words on the representation of decimal numbers as types. While the
> > representation with types of the form D1 (D2 (D3 Sz)) has the advantage
> > of allowing numbers of arbitrary size, it has the disadvantage of a
> > growing number of parantheses.  In my opinion, it would be nicer to have
> > somethink like D1 :- D2 :- D9 :- () with a right-associative operator :-.
> >  We could even build the digit list the other way round—() :- D1 :- D2 :-
> > D9—using a left-associative :-.  With the latter representation, we
> > wouldn't need to reverse digit sequences when adding numbers.
>
> Right, I agree. I think we should use the arbitrary-size implementation

So let’s use the representation with the left-associative :- (or whatever 
operator we might choose).

> (actually, how arbitrary is it? what's the limit of GHC, if any?).

Arbitrary enough, I think.  If we don’t need lists with billions of elements, 
our representations will have less than 8 digits.

> To make it friendlier for the end user I thought about defining
> aliases for lets say the first 10000 numbers using Template Haskell.
> That could even make error reports friendlier (not sure to what point
> though). What do you think?

I have no clear opinion about that at the moment.  Maybe it’s okay to use the 
representation directly.  This way, we don’t introduce a dependeny on the 
Template Haskell language extension (which is only supported by GHC), and the 
actual representation will occur in error messages anyway whenever the 
message shows a computed number.

> So, we'll be making two separate libraries then. We should think about
> names.
>
> What about FixedVector for the vector library and DecTypArith (maybe
> too long) or DecTypes for the type-level decimal arithmetic library?

Alas, there is an inconsistency in naming packages already.  Some prefer names 
which are entirely lowercase, some prefer camel case.  I prefer lowercase, 
with hyphens separating parts of the name.  And I also don’t like unusual 
abbreviations like “typ” (not much shorter than “type”).  To mention 
arithmetics is not so important.  So maybe something 
like “type-level-decimals”?

Maybe it’s better to put different type-level programming things into a single 
package.  Then we could name this package “type-level” or something similar.  
We could start with our decimals.  Other type-level things could be added 
later.  I already have some code about type-level booleans.  It’s not very 
sensible to put these few lines into a separate package.  It might be nice if 
we had a general type-level programming package where I could put this code 
into.

As for the name of the fixed-size list package, I have to say that I don’t 
like the term “vector” in this context.  A vector is actually something with 
addition and scalar multiplication defined on it.  Maybe we should make also 
this package’s scope wider.  What about something like “safe-data” or 
similar?

> I'll put my hands dirty once we agree on this.

Great!!

> Cheers,
>
> Fons

Best wishes,
Wolfgang