[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)

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.


More information about the Haskell-Cafe mailing list