[Haskell-cafe] HList records access time [was: Diving into the records swamp]

[AntC]

> Aleksandar Dimitrov <aleks.dimitrov <at> gmail.com> writes:
>

Hi Aleksandar, I was hoping that Oleg himself would answer the second part 
of your post, as he did the part re DataKinds:
 
> 
> Here's one thing I don't like about the "current" way HList-based 
> extensible record are represented (and used in OOHaskell [2]):
> the access time is linear in
> the number of records a certain type has.
> Somehow just the thought of "reorder the records in your
> constructors to make your program go faster" makes me cringe
> a little.

Yes, it would me!

I thought that usually the instance matching for HList happens at compile 
time(?) So reordering might make compiles faster, but that should be dealt 
with before run-time(?)

I guess it matters whether the 'shape' of the HLists is knowable at 
compile time, or the records are built 'on the fly' at run time.

Here's a possibly relevant idea that I would try for myself if only my day 
job didn't get in the way of my life so much ;-(. 

Instead of Type-Indexed Products (TIP's as the HList paper calls them), 
how about Type-Indexed tuples (TIple's) like this:

    instance Has (a, b)    a where { get (x, _) = x; ... }
    instance Has (a, b)    b ...
    instance Has (a, b, c) a ...
    ...
    instance Has (a, b, c, d) a ...
    ...

(Note that the result type is not an argument to `get'; instead the type 
is 'pulled' out by the demanding context.)

Then access to any element is 'flat' rather than having to walk down the 
spine of an HList. (Again this needs being able to resolve instances at 
compile time.)

The instances for any n-tuple overlap, and the result of get/set is not 
confluent. This only matters if the same type appears twice in a tuple. 
(Contrast that HList uses a 'Lacks' pseudo-constraint/instance failure.)

I hope Template Haskell would help with generating the instances for all 
of the n-tuples -- otherwise it's a lot of boilerplate.

The tricky part comes with TIple-level combinations such as extend or 
append. That might be where NewAxioms overlaps come in to calculate the 
type of the result.

AntC