[Haskell-cafe] Efficient records with arbitrarily many fields [was: Extensible states]

[Ben Franksen]

Marcin Mrotek wrote:
> Okay, perhaps I'm too newbie to understand the big picture, but it
> seems to me you can get either:
> 
> a) O(1) access to any, arbitrarily selected (at runtime) field
> b) O(1) append
> 
> I guess option a) is better performance-wise, as appending is usually
> done less often than selecting (an O(1) slice is already possible with
> independently typed regular Haskell records) but
> dependently-typed-list-based implementation, or at the very least
> Vinyl (I haven't ever used HList) has the advantage of being dead
> simple in both implementation and usage. I mean, with Vinyl, you can
> write manual recursion over Rec's like:
> 
> foo :: Rec ... -> Rec ...
> foo RNil = ...
> foo (r :& rs) = ...
> 
> whenever GHC's typechecker gives up and goes on a strike; and I dare
> to say, with commonly used record sizes (have you ever used a record
> with more than, let's say, 10 fields?) the speed tradeoff is not
> noticeable.

While more than 10 fields in a record is uncommon for typical library APIs 
and simple programs, real world projects can grow much larger records. One 
example is configuration data for complex programs (like Darcs or even GHC) 
with many options. It would be so nice if we could use record types for the 
configuration! Another application could in control system toolkits like 
EPICS [1], which currently has (actually: generates) C records with 
potentially hundreds of fields.

If lookup is / remains linear we can never efficiently support these kinds 
of applications and that would be very sad.

I think the most reasonable default is O(1) for lookup and O(n) for 
extension, like in Nikita Volkov's record package. It is quite unfortunate 
that this package limits the number of fields! If GHC would offer generic 
support for tuples of arbitrary size (with the same efficiency as today) 
this limitation could be avoided and all would be well.

Cheers
Ben

[1] http://www.aps.anl.gov/epics/
-- 
"Make it so they have to reboot after every typo." ― Scott Adams