Newest at the top
| 2026-03-03 19:07:16 +0100 | tromp | (~textual@2001:1c00:3487:1b00:bca6:b25a:741d:ca28) (Quit: My iMac has gone to sleep. ZZZzzz…) |
| 2026-03-03 19:05:33 +0100 | Square2 | (~Square4@user/square) Square |
| 2026-03-03 19:05:30 +0100 | <EvanR> | this is why it's better not to look at academic research and reinvent everything from the wheel. No way to know if the paper's right! |
| 2026-03-03 19:00:47 +0100 | durstloescher | (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) (Quit: My Mac has gone to sleep. ZZZzzz…) |
| 2026-03-03 18:57:48 +0100 | <c_wraith> | There were actually two bugs in those libraries. One was that they tried to optimize inserting to an empty tree and got the logic wrong so that it didn't balance repeated insertions on the same side. The other was that the paper they were working from misread one of its references and so missed an important part of the balancing algorithm's weight comparisons. |
| 2026-03-03 18:56:34 +0100 | Square2 | (~Square4@user/square) (Ping timeout: 245 seconds) |
| 2026-03-03 18:56:24 +0100 | oskarw | (~user@user/oskarw) (Remote host closed the connection) |
| 2026-03-03 18:55:16 +0100 | yin | (~zero@user/zero) zero |
| 2026-03-03 18:55:11 +0100 | durstloescher | (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) |
| 2026-03-03 18:54:22 +0100 | tzh | (~tzh@c-76-115-131-146.hsd1.or.comcast.net) tzh |
| 2026-03-03 18:53:30 +0100 | durstloescher | (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) (Quit: My Mac has gone to sleep. ZZZzzz…) |
| 2026-03-03 18:52:13 +0100 | u0_a216 | (~molidae@2401:4900:6289:5b82:f04f:39fd:d52a:6874) |
| 2026-03-03 18:51:55 +0100 | yin | (~zero@user/zero) (Ping timeout: 264 seconds) |
| 2026-03-03 18:50:08 +0100 | Guest5338 | (~john@cpc157419-sotn14-2-0-cust964.15-1.cable.virginm.net) (Ping timeout: 252 seconds) |
| 2026-03-03 18:48:10 +0100 | jtnuttall | (~jeremy@user/jeremyn) jeremyn |
| 2026-03-03 18:44:22 +0100 | yin | (~zero@user/zero) zero |
| 2026-03-03 18:39:55 +0100 | yin | (~zero@user/zero) (Ping timeout: 264 seconds) |
| 2026-03-03 18:38:53 +0100 | madresch | (~Thunderbi@user/madresch) (Ping timeout: 268 seconds) |
| 2026-03-03 18:33:45 +0100 | yin | (~zero@user/zero) zero |
| 2026-03-03 18:31:26 +0100 | yin | (~zero@user/zero) (Ping timeout: 252 seconds) |
| 2026-03-03 18:27:15 +0100 | n0w0n | Guest5338 |
| 2026-03-03 18:26:52 +0100 | n0w0n | (~john@cpc157419-sotn14-2-0-cust964.15-1.cable.virginm.net) |
| 2026-03-03 18:23:01 +0100 | <EvanR> | oof |
| 2026-03-03 18:22:11 +0100 | sord937 | (~sord937@gateway/tor-sasl/sord937) (Quit: sord937) |
| 2026-03-03 18:13:36 +0100 | chromoblob | (~chromoblo@user/chromob1ot1c) chromoblob\0 |
| 2026-03-03 18:12:52 +0100 | <c_wraith> | I feel relatively competent addressing its balancing algorithm, because it's the same one used in the priority search pennants a couple different libraries used that I ended up spending a lot of time investigating a year ago after my AoC solution to one problem found a balancing error. |
| 2026-03-03 18:10:23 +0100 | wbrawner | (~wbrawner@129.146.105.153) wbrawner |
| 2026-03-03 18:08:05 +0100 | wbrawner | (~wbrawner@129.146.105.153) (Ping timeout: 245 seconds) |
| 2026-03-03 18:06:26 +0100 | fgarcia | (~lei@user/fgarcia) (Ping timeout: 248 seconds) |
| 2026-03-03 18:06:11 +0100 | <c_wraith> | (the proof that it's correct is complicated, but the algorithm is simple) |
| 2026-03-03 18:05:25 +0100 | <c_wraith> | it just checks the ratio of the sizes of the children of a node, and acts if it exceeds its threshold. |
| 2026-03-03 18:04:28 +0100 | <c_wraith> | the nice thing about the tree implementation in containers is that balancing is is a fixup pass after a modification that's oblivious to what the modification was. |
| 2026-03-03 18:03:39 +0100 | <haskellbridge> | <ijouw> I cannot remember if I ever had to implement deletion. Will try |
| 2026-03-03 18:02:16 +0100 | <gentauro> | EvanR: deleting in RB-trees is really really complex |
| 2026-03-03 18:01:55 +0100 | durstloescher | (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) |
| 2026-03-03 18:00:17 +0100 | <haskellbridge> | <ijouw> Ah, no. |
| 2026-03-03 17:59:10 +0100 | <haskellbridge> | <ijouw> Doesn't Set use Red Black trees? |
| 2026-03-03 17:56:32 +0100 | durstloescher | (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) (Quit: My Mac has gone to sleep. ZZZzzz…) |
| 2026-03-03 17:55:11 +0100 | jmcantrell_ | (~weechat@user/jmcantrell) jmcantrell |
| 2026-03-03 17:49:52 +0100 | <EvanR> | red black tree is kind of complicated isn't it, or is it sort of educational value for leading up to our "industrial" trees we use in haskell? |
| 2026-03-03 17:47:49 +0100 | acidjnk_new3 | (~acidjnk@p200300d6e700e523af5c13a8fba9f168.dip0.t-ipconnect.de) (Ping timeout: 245 seconds) |
| 2026-03-03 17:47:15 +0100 | <gentauro> | durstloescher: I have provided `insert`. It's up to the reader to implement the `delete` logic for the `RB-Trees` (muahahaha) |
| 2026-03-03 17:46:29 +0100 | <gentauro> | durstloescher: here I use it (RB-Tree) for my `Set`. It can easily be used to create `Map` as well (just provide a tuple pair) -> https://paste.tomsmeding.com/K9QzYIJM |
| 2026-03-03 17:46:03 +0100 | akegalj | (~akegalj@78-1-128-213.adsl.net.t-com.hr) (Quit: leaving) |
| 2026-03-03 17:45:41 +0100 | <durstloescher> | thank you all i'll look into the book and try the provided code snippet <3 |
| 2026-03-03 17:43:58 +0100 | <gentauro> | I think ACM now is free to read iirc |
| 2026-03-03 17:43:38 +0100 | <gentauro> | durstloescher: I would highly recommend you to read Okasaki Functional Pearl "Red-Black Trees in a Functional Setting" |
| 2026-03-03 17:43:04 +0100 | tmu | (~tmu@71.227.230.155) |
| 2026-03-03 17:40:31 +0100 | jtnuttall | (~jeremy@user/jeremyn) (Ping timeout: 264 seconds) |
| 2026-03-03 17:39:30 +0100 | Googulator46 | (~Googulato@2a01-036d-0106-0119-2546-5dd3-b1b8-39cd.pool6.digikabel.hu) |