<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; " class="">Hi Milan,<div class="" style=""><br class="" style=""><div style=""><div class="" style="">On 03.03.2010, at 15:23, Milan Straka wrote:</div><br class="Apple-interchange-newline" style=""><blockquote type="cite"><div class="" style="">Hi all,<br class="" style=""><br class="" style="">I have started an internship in Cambridge and will spend 3 months on<br class="" style="">Haskell. One of the possible projects is improving the containers<br class="" style="">library. Things I am thinking about:<br class="" style="">- measuring the performance of existing implementations (notably Map and<br class="" style=""> Set) and possibly improve them (either without or with API changes),<br class="" style="">- adding Queue and a PriorityQueue,<br class="" style="">- maybe adding a generalized trie,<br class="" style="">- maybe adding a hashtable (more like a trie of the hashes, something in<br class="" style=""> the line of Ideal hash trees; and maybe a 'classic' hash modifiable in<br class="" style=""> the ST monad?)<br class="" style=""><br class="" style="">I would be grateful for any comments, thoughts or wishes.<br class="" style=""></div></blockquote></div><br class="" style=""></div><div class="" style="">In the context of program analysis, one tracks a lot of information about the state of a program at a given program point. This state is propagated around loops and conditionals. The implicit sharing of nodes in functional data structures are very well suited for this.</div><div class="" style=""><br class="" style=""></div><div class="" style="">However, whenever two states need to be joined at the loop head or at the end of a conditional, the two trees that represent the state need to be joined by performing some sort of join operation on each element of a tree. For all sensible domains a `join` a = a. Given that a loop or branch of a conditional usually touches only few variables, it is prudent not to perform the join operation on all elements of the tree. Instead, a tree-difference operation is required that traverses the two trees to be joined and calculates the difference between them. In particular, whenever two references are, in fact, the same pointer, the subtree does not need to be considered. This way, a join between two trees of size n reduces to joining only m elements where m is the maximum number of elements in each tree. This is a tremendous win for n >> m.</div><div class="" style=""><br class="" style=""></div><div class="" style="">I've implemented such a difference operation on a home-grown splay tree implementation. I would like to see this on standard AVL trees. Maybe other people could indicate if such a difference operation on trees would be useful in their applications.</div><div class="" style=""><br class="" style=""></div><div class="" style="">The difference operation in my implementation has the following signature:</div><div class="" style=""><br class="" style=""></div><div class="" style=""><span class="Apple-style-span" style="font-family: sans-serif; "><table class="vanilla" cellspacing="0" cellpadding="0" style="width: 1001px; border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; position: static; z-index: auto; "><tbody><tr><td class="decl" style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; padding-top: 2px; padding-right: 2px; padding-bottom: 2px; padding-left: 2px; background-color: rgb(240, 240, 240); font-family: monospace; vertical-align: top; "><b>difference</b> :: (<a href="file:///Library/Frameworks/GHC.framework/Versions/610/usr/share/doc/ghc/libraries/base/Data-Ord.html#t%3AOrd" style="color: rgb(0, 0, 224); text-decoration: none; ">Ord</a> k) => (a -> a -> <a href="file:///Library/Frameworks/GHC.framework/Versions/610/usr/share/doc/ghc/libraries/ghc-prim/GHC-Bool.html#t%3ABool" style="color: rgb(0, 0, 224); text-decoration: none; ">Bool</a>) -> <a href="file:///Users/simona/current/source/hsdata/dist/doc/html/hsdata/Data-SplayTreePure.html#t%3AMap" style="color: rgb(0, 0, 224); text-decoration: none; ">Map</a> k a -> <a href="file:///Users/simona/current/source/hsdata/dist/doc/html/hsdata/Data-SplayTreePure.html#t%3AMap" style="color: rgb(0, 0, 224); text-decoration: none; ">Map</a> k a -> ([k], [k])</td></tr><tr><td class="doc" style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; padding-top: 2px; padding-left: 10px; ">Calculate the difference between the two trees. Returns the elements that were in the first but not in the second and the elements that were in the second but not in the first. Both lists are unsorted. In case two element have the same key the given equality predicate is a applied to them. If the predicate returns <tt style="font-size: 13px; ">False</tt> the elements are added to their respective difference lists. The contents of both trees remain unchanged.</td></tr><tr><td class="s15" style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; height: 15px; "></td></tr><tr><td class="decl" style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; padding-top: 2px; padding-right: 2px; padding-bottom: 2px; padding-left: 2px; background-color: rgb(240, 240, 240); font-family: monospace; vertical-align: top; "><a name="v:differenceElems"></a><a name="v%3AdifferenceElems"></a><b>differenceElems</b> :: (<a href="file:///Library/Frameworks/GHC.framework/Versions/610/usr/share/doc/ghc/libraries/base/Data-Ord.html#t%3AOrd" style="color: rgb(0, 0, 224); text-decoration: none; ">Ord</a> k) => (a -> a -> <a href="file:///Library/Frameworks/GHC.framework/Versions/610/usr/share/doc/ghc/libraries/ghc-prim/GHC-Bool.html#t%3ABool" style="color: rgb(0, 0, 224); text-decoration: none; ">Bool</a>) -> <a href="file:///Users/simona/current/source/hsdata/dist/doc/html/hsdata/Data-SplayTreePure.html#t%3AMap" style="color: rgb(0, 0, 224); text-decoration: none; ">Map</a> k a -> <a href="file:///Users/simona/current/source/hsdata/dist/doc/html/hsdata/Data-SplayTreePure.html#t%3AMap" style="color: rgb(0, 0, 224); text-decoration: none; ">Map</a> k a -> ([a], [a])</td></tr><tr><td class="doc" style="border-top-width: 0px; border-right-width: 0px; border-bottom-width: 0px; border-left-width: 0px; padding-top: 2px; padding-left: 10px; ">As <tt style="font-size: 13px; "><a href="file:///Users/simona/current/source/hsdata/dist/doc/html/hsdata/Data-SplayTreePure.html#v%3Adifference" style="color: rgb(0, 0, 160); text-decoration: none; ">difference</a></tt>, but extracts the elements, not their keys.</td></tr></tbody></table><br class="" style=""></span></div><div class="" style=""><font class="Apple-style-span" face="sans-serif">Cheers,</font></div><div class="" style=""><font class="Apple-style-span" face="sans-serif">Axel</font></div></body></html>