<HTML><BODY><div id="composeWebView_editable_content" data-mailruapp-compose-id="composeWebView_editable_content" style="text-align: left;"><div>Firstly, to correct myself:</div><div><br></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 </span><br></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><br></div><div>But I have some q's about the optimisations:</div><div>The hedge-union algorithm seems to have been taken out, as inefficient.</div><div>(per treeowl on github). But the code on hackage still uses hedge??</div><div>So the docos are out of date. (And quite a bit of commentary on StackOverflow.) </div><div>Was it really not more efficient?</div><div><br></div><div>The Set data type's constructors got reordered (Bin is now first, Tip is second).</div><div>On grounds it "improves the benchmark by up to 10%".</div><div>Are you sure it makes that much difference?</div><div>Are you sure it makes any difference at all?</div><div id="mail-app-auto-signature"></div>The culprit seems to be pattern matching. It makes me feel there's something seriously wrong with GHC's code generator.<div>(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<div>unlike imperative/low-level implementations of balanced binary trees.</div><div>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?</div><div><br></div><div>Contrast that in an imperative/low-level model they'd be null pointers, nothing allocated.</div><div>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?</div><div>| both sub-trees are empty </div><div>| left (only) is empty</div><div>| right (only) is empty</div><div><br></div><div>If it's true per above that each constructor adds a performance penalty just doing the pattern matching, I guess the answer is 'no' :-(</div><div><br></div><div>Thanks</div><div>AntC</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_14709423600000000687_BODY"><br>
</div>
<base target="_self" href="https://e-aj.my.com/">
</div>
</div>
</blockquote></div></div></div><style type="text/css"></style></div></BODY></HTML>