<p dir="ltr">I think there are many cases where some standard data type (that is not a list) is paired with type-level lists:</p>
<p dir="ltr">I've tried the (unboxed) array case with<a href="http://code.haskell.org/HList/Data/HList/broken/RecordU.hs"> http://code.haskell.org/HList/Data/HList/broken/RecordU.hs</a> (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.</p>
<p dir="ltr">CTRex<a href="https://github.com/atzeus/CTRex"> https://github.com/atzeus/CTRex</a> does that dynamic+hash map idea.</p>
<p dir="ltr">Another example is<a href="https://github.com/nikita-volkov/record"> </a><a href="https://github.com/nikita-volkov/record">https</a><a href="https://github.com/nikita-volkov/record">://</a><a href="https://github.com/nikita-volkov/record">github.com</a><a href="https://github.com/nikita-volkov/record">/</a><a href="https://github.com/nikita-volkov/record">nikita-volkov</a><a href="https://github.com/nikita-volkov/record">/record</a> using one data type for each length supported<br>
</p>
<div class="gmail_quot<blockquote class=" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Just as an afterthought about the O(n) lookup issue - extensible<br>
records are dependently typed versions of old, well-known data<br>
structures, so you always have a trade off between lookup and<br>
appending. In Haskell it's relatively easy to implement dependently<br>
typed lists (Vinyl, HList, etc), or maps (?) (apparently, Extensible<br>
linked by Adam, but I admit I haven't looked into the code).<br>
Dependently typed arrays are trickier. I guess it could be, for<br>
example, hacked around a (Vector Dynamic), then using (fromJust .<br>
fromDynamic) when it's certain at compile time that a there's a value<br>
of a certain type hidden in there, but I'm not sure if anyone has<br>
actually implemented it. They would necessarily have O(n) append,<br>
though.<br>
<br>
Best regards,<br>
Marcin Mrotek<br>
</div>