<story><title>Efficient Immutable Collections [pdf]</title><url>https://michael.steindorfer.name/publications/phd-thesis-efficient-immutable-collections.pdf</url></story><parent_chain></parent_chain><comment><author>jb1991</author><text>To anyone wondering why stuff like this matters, it&amp;#x27;s because the benefits of functional programming reach new heights when coupled with efficient immutable structures. In C++, for example, you can do functional programming in the most basic sense of the word, and it&amp;#x27;s actually pretty fun. But it can be very expensive because you are not working on efficient data structures that support the mangling and idioms that make FP really shine. There have been interesting efforts to bring structures like this to C++ but nothing mature or known widespread. When people talk about FP, it&amp;#x27;s about a lot more than what you can do with functions and expressions; it&amp;#x27;s about making sure that these functional manipulations remain very fast without lots of copying, and that&amp;#x27;s what is so fascinating about data structure research: how it supports new ways to write programs.</text></comment>
<story><title>Efficient Immutable Collections [pdf]</title><url>https://michael.steindorfer.name/publications/phd-thesis-efficient-immutable-collections.pdf</url></story><parent_chain></parent_chain><comment><author>norswap</author><text>This is really cool work by Michael, a collection of configurable data structures.&lt;p&gt;Underlying most of them is CHAMP - a compressed hash array map trie. Essentially it&amp;#x27;s a trie over the hash of the objects inserted in the map. It&amp;#x27;s compressed using a clever technique that involves bitmaps.&lt;p&gt;A made a toy implementation of it to get a sense of how it works. There are some accompanying notes that you might find useful: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;norswap&amp;#x2F;triemap&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;norswap&amp;#x2F;triemap&lt;/a&gt;</text></comment>