[Haskell-cafe] Re: Implementing fixed-sized vectors (using
g9ks157k at acme.softbase.org
Fri Feb 1 16:32:16 EST 2008
Am Freitag, 1. Februar 2008 13:00 schrieb Alfonso Acosta:
> On Jan 31, 2008 11:35 PM, Wolfgang Jeltsch <g9ks157k at acme.softbase.org>
> > 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
> 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
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
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
> I'll put my hands dirty once we agree on this.
More information about the Haskell-Cafe