Hmmmkay. I'm not entirely convinced, 'cause I've seen genuine (and benchmarked) speedups in applying some of these ideas to my TrieMap library, but I don't have any examples handy.<br><br clear="all">Louis Wasserman<br>
<a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a><br><a href="http://profiles.google.com/wasserman.louis">http://profiles.google.com/wasserman.louis</a><br>
<br><br><div class="gmail_quote">On Tue, Feb 22, 2011 at 9:10 PM, Johan Tibell <span dir="ltr"><<a href="mailto:johan.tibell@gmail.com">johan.tibell@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
On Tue, Feb 22, 2011 at 6:53 PM, Louis Wasserman<br>
<div class="im"><<a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a>> wrote:<br>
</div><div class="im">> Here's the approach I was attempting: a while back there was a proposal to<br>
> modify Data.Map to support a sort of zipper, including the following API:<br>
><br>
> data Location k a -- represents a map with a "hole" at a particular key<br>
><br>
> search :: k -> Map k a -> (Maybe a, Location k a)<br>
><br>
> key :: Location k a -> k<br>
><br>
> assign :: a -> Location k a -> Map k a<br>
> clear :: Location k a -> Map k a<br>
><br>
> and from here you might define<br>
><br>
> insert :: k -> a -> Map k a -> Map k a<br>
> insert k a m = case search k m of<br>
> (_, loc) -> assign a loc<br>
><br>
> The surprising thing was that this approach *increased* the speed of the Map<br>
> implementation by something like 7%.<br>
<br>
</div>I'm pretty sure it was a decrease overall. The function under<br>
discussion was something like insertWith.<br>
<br>
The direct implementation of insertWith was the fastest. The zipper<br>
approach was 7% faster than using a naive composition of lookup and<br>
insert to implement insertWith. The slowdown was most likely caused by<br>
the extra O(log n) allocations required to create the zipper (in<br>
essence that means reify the call stack of lookup).<br>
<font color="#888888"><br>
Johan<br>
</font></blockquote></div><br>