<HTML><BODY><div id="composeWebView_editable_content" data-mailruapp-compose-id="composeWebView_editable_content" style="text-align: left;"><div><div><span style="background-color: rgba(255, 255, 255, 0);">Firstly, to correct myself:</span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">> Contrast that with Data.Set [*], you could stream the contents to a list and filter.</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">> (Which would be horribly inefficient for my purposes.) </span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">Thank you Libraries team. Data.Set seems to have been seriously revamped since I last looked, and now includes a 'proper' filter function. (It used to stream the Set to a List; filter the List; build a new Set.)</span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">> [*] Data.Set seems to have been swallowed into the new collections library,</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">> which is not currently maintained <br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">Uhh. That was a dead link (of ~10 years ago, but Google still took me to it). Data.Set is in the **containers** library supported on hackage.</span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">But I have some q's about the optimisations:</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">The hedge-union algorithm seems to have been taken out, as inefficient.</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">(per treeowl on github). But the code on hackage still uses hedge??</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">So the docos are out of date. (And quite a bit of commentary on StackOverflow.) </span></div><div><span style="background-color: rgba(255, 255, 255, 0);">Was it really not more efficient?</span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">The Set data type's constructors got reordered (Bin is now first, Tip is second).</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">On grounds it "improves the benchmark by up to 10%".</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">Are you sure it makes that much difference?</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">Are you sure it makes any difference at all?</span></div><div></div><span style="background-color: rgba(255, 255, 255, 0);">The culprit seems to be pattern matching. It makes me feel there's something seriously wrong with GHC's code generator.</span><div><span style="background-color: rgba(255, 255, 255, 0);">(And the semantics of ADTs is that the first constructor is ordered first if you go `deriving (Ord)`. So there's usually a design reason driving the ordering of constructors -- eg Nothing ordered before Just; [] ordered before (:), which makes String ordering do the right thing.)<br><br>Set is a purely functional data structure, no in-situ updating of nodes, no pointer semantics</span><div><span style="background-color: rgba(255, 255, 255, 0);">unlike imperative/low-level implementations of balanced binary trees.</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">That means Tips (empty end-points) genuinely get allocated/built and accessed and garbaged on insert -- or does all that strictness annotation/INLINing alter that?</span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">Contrast that in an imperative/low-level model they'd be null pointers, nothing allocated.</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">Note the number of Tips is equal the number of values in the tree, + 1.<br>Would it save construction/destruction/access overhead to have three extra constructors?</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">| both sub-trees are empty </span></div><div><span style="background-color: rgba(255, 255, 255, 0);">| left (only) is empty</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">| right (only) is empty</span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">If it's true per above that each constructor adds a performance penalty just doing the pattern matching, I guess the answer is 'no' :-(</span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><span style="background-color: rgba(255, 255, 255, 0);">Thanks</span></div><div><span style="background-color: rgba(255, 255, 255, 0);">AntC</span></div><div><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div><div data-mailruapp-compose-id="composeWebView_previouse_content"><blockquote style="border-left-width: 1px; border-left-style: solid; border-left-color: rgb(252, 44, 56); margin: 10px 10px 10px 5px; padding: 0px 0px 0px 10px;"><div></div></blockquote></div></div></div></div><div id="composeWebView_previouse_content" data-mailruapp-compose-id="composeWebView_previouse_content"><blockquote id="mail-app-auto-quote" style="border-left: 1px solid #fc2c38; margin: 10px 10px 10px 5px; padding: 0 0 0 10px;"><div class="js-helper js-readmsg-msg"><div><div id="style_14711719780000000538_BODY"><div data-mailruapp-compose-id="composeWebView_editable_content" style="text-align: left;"><div data-mailruapp-compose-id="composeWebView_previouse_content"><blockquote style="border-left: 1px solid #fc2c38;margin: 10px 10px 10px 5px;padding: 0 0 0 10px;"><div><div><div><br>
</div>
</div>
</div>
</blockquote></div></div>
</div>
<base target="_self" href="https://e-aj.my.com/">
</div>
</div>
</blockquote></div><style type="text/css"></style></div></BODY></HTML>