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

Am Freitag, 1. Februar 2008 13:00 schrieb Alfonso Acosta:

On Jan 31, 2008 11:35 PM, Wolfgang Jeltsch 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