[Haskell-cafe] Extensible states

adam vogt vogt.adam at gmail.com
Wed May 6 17:32:48 UTC 2015


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/record>https
<https://github.com/nikita-volkov/record>://
<https://github.com/nikita-volkov/record>github.com
<https://github.com/nikita-volkov/record>/
<https://github.com/nikita-volkov/record>nikita-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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150506/cd0b3060/attachment.html>


More information about the Haskell-Cafe mailing list