I think there are many cases where some standard data type (that is not a list) is paired with type-level lists: I've tried the (unboxed) array case with http://code.haskell.org/HList/Data/HList/broken/RecordU.hs (worked with ghc 7.8), but it didn't seem to be any faster in my tests: I have a feeling that the index into the array should not be calculated as 1+1+1+1: the author of extensible does something that looks better. CTRex https://github.com/atzeus/CTRex does that dynamic+hash map idea. Another example is https://github.com/nikita-volkov/recordhttps https://github.com/nikita-volkov/record:// https://github.com/nikita-volkov/recordgithub.com https://github.com/nikita-volkov/record/ https://github.com/nikita-volkov/recordnikita-volkov https://github.com/nikita-volkov/record/record https://github.com/nikita-volkov/record using one data type for each length supported 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