<div dir="ltr">In the following paper we introduced an implementation that performs lookup in O(log n) and insertion in O(1) by moving some of the work to compile time.<div><br></div><div><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">@INPROCEEDINGS { MVP13,</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    AUTHOR = { Martinez, Bruno and Viera, Marcos and Pardo, Alberto },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    TITLE = { Just Do It While Compiling!: Fast Extensible Records in Haskell },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    BOOKTITLE = { Proceedings of the ACM SIGPLAN 2013 Workshop on Partial Evaluation and Program Manipulation },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    SERIES = { PEPM '13 },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    YEAR = { 2013 },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    ISBN = { 978-1-4503-1842-6 },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    LOCATION = { Rome, Italy },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    PAGES = { 77--86 },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    NUMPAGES = { 10 },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    DOI = { 10.1145/2426890.2426908 },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    ACMID = { 2426908 },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    PUBLISHER = { ACM },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    ADDRESS = { New York, NY, USA },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    KEYWORDS = { balanced trees, extensible records, haskell, hlist, staged computation, type-level programming },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">    PDF = { </span><a class="" href="http://www.fing.edu.uy/~mviera/papers/pepm13.pdf" rel="nofollow" style="text-decoration:none;color:rgb(0,102,204);font-family:monospace;font-size:12px;line-height:18px">http://www.fing.edu.uy/~mviera/papers/pepm13.pdf</a><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"> },</span><br style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">}</span><br></div><div><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><br></span></div><div><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px">Best,</span></div><div><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"> marcos</span></div><div><span style="color:rgb(51,51,51);font-family:monospace;font-size:12px;line-height:18px"><br></span></div><div><span style="color:rgb(51,51,51);font-family:Verdana,Helvetica,sans-serif;font-size:12px;line-height:18px"><br></span></div><div><span style="color:rgb(51,51,51);font-family:Verdana,Helvetica,sans-serif;font-size:12px;line-height:18px"><br></span></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 5, 2015 at 6:50 AM, Roman Cheplyaka <span dir="ltr"><<a href="mailto:roma@ro-che.info" target="_blank">roma@ro-che.info</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On 05/05/15 12:40, Alberto G. Corona  wrote:<br>
> Hi,<br>
><br>
> Anyone used some of the extensible record packages to create a kind of<br>
> extensible state monad?<br>
><br>
> I mean something that besides having "get", "gets" and "put"  would have<br>
> some kind of "add" and "gets":<br>
><br>
> add :: a -> State ()<br>
> gets  :: State (Maybe a)<br>
><br>
> or<br>
><br>
> add :: LabelName -> a -> State ()<br>
> gets :: LabelName -> State (Maybe a)<br>
><br>
><br>
> So that I can extend the state without using additional monad<br>
> transformers. Monad transformers are very hard for beginners and<br>
> scramble error messages<br>
><br>
> I did the first option for MFlow, hplayground and Transient packages<br>
> (setSData and getSData). But my solution uses a map indexed by type and<br>
> this requires a lookup for each access.<br>
><br>
> I would like to know if there is an alternative with no lookups. I´m not<br>
> obsessed with speed but In some applications the speed may be important....<br>
><br>
> Anyone?<br>
<br>
<br>
</div></div>If you care about the error message quality, you'd rather stay away from<br>
extensible records.<br>
<br>
And if you care about speed, most (all?) extensible records give you<br>
O(n) access, so you'd be actually better off with a simple (Hash)Map.<br>
<span class="HOEnZb"><font color="#888888"><br>
Roman<br>
<br>
</font></span><br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div></div>