[Haskell-cafe] Records vs HList

[David Menendez]

Keean Schupke writes:

> David Menendez wrote:
> 
> >Chris Kuklewicz writes:
> >
> >>Would the record system describe at
> >>http://lambda-the-ultimate.org/node/view/1119
> >>also be convertable "into System Fw, GHC's existing, strongly-typeed
> >>intermediate language." ?
> >
> >Probably. Daan's current implementation uses MLF, which I believe is
> >system F implemented for ML.
> >
> >(We're talking about the system in Daan Leijen's paper, "Extensible
> >Records With Scoped Labels". Good stuff.)
>
> You can change the project and update operators in the HList library
> to behave in exactly this way. At the moment they are constrained to
> not allow multiple identical labels in records. If this kind of
> access is considered useful, I can add it to the HList distribution.

This is true. I've implemented a small subset of HList that's able to
emulate Daan's three record operators using only fundeps and undecidable
instances.

    *Main> let r = foo .=. "Bar" .*. emptyRecord
    *Main> r
    Record{foo="Bar"}
    *Main> let r2 = foo .=. () .*. r          
    *Main> r2
    Record{foo=(),foo="Bar"}
    *Main> r2 .!. foo
    ()
    *Main> (r2 .-. foo) .!. foo
    "Bar"

(This is actually *more* powerful than the system described in Daan's
paper, because labels are first class.)

While this is a testament to the power of Haskell's extended type-class
system, I'm not sure that it can replace a dedicated record system. In
his paper, Daan describes how to implement the records such that field
lookups take O(log n) or even O(1) time. HList can't do better than
O(n).

Of course, in the absence of a powerful record system, HList is the way
to go. Rather than decide on a new record system sight unseen, let's
implement them using HList and see how they feel.
-- 
David Menendez <zednenem at psualum.com> | "In this house, we obey the laws
<http://www.eyrie.org/~zednenem>      |        of thermodynamics!"