Okay, perhaps I'm too newbie to understand the big picture, but it seems to me you can get either: a) O(1) access to any, arbitrarily selected (at runtime) field b) O(1) append I guess option a) is better performance-wise, as appending is usually done less often than selecting (an O(1) slice is already possible with independently typed regular Haskell records) but dependently-typed-list-based implementation, or at the very least Vinyl (I haven't ever used HList) has the advantage of being dead simple in both implementation and usage. I mean, with Vinyl, you can write manual recursion over Rec's like: foo :: Rec ... -> Rec ... foo RNil = ... foo (r :& rs) = ... whenever GHC's typechecker gives up and goes on a strike; and I dare to say, with commonly used record sizes (have you ever used a record with more than, let's say, 10 fields?) the speed tradeoff is not noticeable. Don't get me wrong, I'm all in for cutting edge solutions like the one mentioned by Marcos, but I do think that rejecting the existing ones based on the non-constant time lookup is just premature optimisation. Best regards, Marcin Mrotek