[Haskell] Proposal: Allow "\=" for field update in record update syntax

Keean Schupke k.schupke at imperial.ac.uk
Wed Mar 2 13:51:21 EST 2005

Ben Rudiak-Gould wrote:

> It does. An HList of Int,Bool,Char is isomorphic to the type 
> (Int,(Bool,(Char,()))), and selecting the Bool element will ultimately 
> compile to code like this:
>    case list of
>      (_,(x,_)) -> ...
> It doesn't need to search for the right element at runtime, and it 
> doesn't need to check for end-of-list at runtime, but it does need to 
> deconstruct O(n) pairs at runtime. A statically balanced tree 
> structure would reduce that the O(log n), but I doubt it would improve 
> performance for typical record sizes.
> Of course, inlining may well lead to something like
>    case (a,(b,(c,()))) of
>      (_,(x,_)) -> ...
> which can be optimized away.

You are right, but opening a tuple is quite cheap I would hope. I have 
coded arbitrary binary products, which could be used to write a tree, 
but the classes
would be more complex. The interface would be the same though, so we could
swap the implementation in future to a more efficient one.

Infact there is a tradeoff. Records with faster read times (ie offset 
tables) have slower write times as the table needs to be copied and 
expanded. The list based records have the fastest extention time (for 
the tree we must search for the next free node, with the list we just 
apply one tuple).


More information about the Haskell mailing list