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).
Keean. _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
