[Haskell-cafe] Re: Records vs HList

[Keean Schupke]

David Menendez wrote:

>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.E
>  
>
Exactly! I like the idea of being able to construct and modify the 
semantics of a record system
(and with the stuff in the OOHaskell paper you can play with Object 
systems in the same way).

The important point with HLists is not that record syntax should not be 
added to Haskell, but
that we can translate it to the existing type system with no conflicts. 
(ie the type system does not
need to be extended there just needs to be some syntax, with an 
optimised implementation)

HList can do O(log n) by the way, if the labels have order, you can 
implement a binary search
tree of labels (Of course all the accessor functions would need to be 
rewritten).

I wonder if some syntactic support for label creation would make things 
nicer.

Actually one really useful change I would like would be to define type 
class functions over all tuples,
that way you could write O(1) accessor functions on tuples using peano 
number indexes.

class TupleIdx u i t | u i -> t where
    idx :: u -> i -> t
instance (a,b) HNil a where
    (a,_) _ = a
instance (a,b) (HSucc HNil) b where
    (_,b) _ = b
instance (a,b,c) HNil a where
    (a,_,_) = a
instance (a,b,c) (HSucc HNil) b where
    (_,b,_) = b
instance (a,b,c) (HSucc (HSucc HNil)) c where
    (_,_,c) = c

etc...

However I haven't thought very hard about how to represent the complete 
(infinite) set
of instances, but using this you can write products of tuples, and 
create records with O(1)
access times from a pair of tuples.

    Keean