[Haskell-cafe] Re: Records vs HList

Keean Schupke k.schupke at imperial.ac.uk
Thu Nov 24 06:31:24 EST 2005


David Menendez wrote:

>Keean Schupke writes:
>
>  
>
>>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).
>>    
>>
>
>The idea of writing a type-level balanced binary search tree fills me
>with an uncertain mixture of excitement and dread. Particularly if you
>want to be able to compare records for equality.
>  
>
Hmm... You have to write and define what you mean by equality
for normal HList records anyway. As you need to ignore the order
of elements the equality test is effectively:

a == b  if  (a `subset` b) and (b `subset` a)

The test for "a subset b" tests if each element in a exists in b.

With an ordered tree, the labels must be in the same order, so
the equality just has to compare elements is a consistant (say pre-order)
way.

In the end HList records were written as they are for clarity in the paper,
and not really as a number-crunching implementation. I find them fast
enough for database work, where the records represent the query (in terms
of projections) and the result table in a type safe way... Infact my 
simple DB
library goes quite a way beyond what HaskellDB can do, mainy due to the
complex type-mechanics being hidden inside the HList/record library.

    Keean.


More information about the Haskell-Cafe mailing list