Just as an afterthought about the O(n) lookup issue - extensible records are dependently typed versions of old, well-known data structures, so you always have a trade off between lookup and appending. In Haskell it's relatively easy to implement dependently typed lists (Vinyl, HList, etc), or maps (?) (apparently, Extensible linked by Adam, but I admit I haven't looked into the code). Dependently typed arrays are trickier. I guess it could be, for example, hacked around a (Vector Dynamic), then using (fromJust . fromDynamic) when it's certain at compile time that a there's a value of a certain type hidden in there, but I'm not sure if anyone has actually implemented it. They would necessarily have O(n) append, though. Best regards, Marcin Mrotek