Logs: liberachat/#haskell
| 2026-03-03 15:51:45 | × | misterfish quits (~misterfis@31-161-39-137.biz.kpn.net) (Ping timeout: 246 seconds) |
| 2026-03-03 15:54:45 | × | chromoblob quits (~chromoblo@user/chromob1ot1c) (Ping timeout: 245 seconds) |
| 2026-03-03 15:58:09 | × | elainedastolat quits (~m@2804:3d14:4b:de00:b20e:16f9:f4d1:21e4) (Quit: Leaving) |
| 2026-03-03 16:01:17 | × | chexum quits (~quassel@gateway/tor-sasl/chexum) (Remote host closed the connection) |
| 2026-03-03 16:01:45 | → | chexum joins (~quassel@gateway/tor-sasl/chexum) |
| 2026-03-03 16:05:06 | → | chromoblob joins (~chromoblo@user/chromob1ot1c) |
| 2026-03-03 16:07:41 | → | durstloescher joins (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) |
| 2026-03-03 16:09:18 | × | chromoblob quits (~chromoblo@user/chromob1ot1c) (Ping timeout: 255 seconds) |
| 2026-03-03 16:14:58 | × | pavonia quits (~user@user/siracusa) (Quit: Bye!) |
| 2026-03-03 16:18:47 | → | humasect joins (~humasect@dyn-192-249-132-90.nexicom.net) |
| 2026-03-03 16:20:43 | → | tromp joins (~textual@2001:1c00:3487:1b00:bca6:b25a:741d:ca28) |
| 2026-03-03 16:30:09 | × | humasect quits (~humasect@dyn-192-249-132-90.nexicom.net) (Remote host closed the connection) |
| 2026-03-03 16:35:32 | <EvanR> | durstloescher, search k1 (Branch k2 v l r) = case compare k1 k2 of {EQ -> v; LT -> search k1 l; GT -> search k2 r} |
| 2026-03-03 16:36:27 | <EvanR> | (for the case of an infinite tree with all branches) |
| 2026-03-03 16:37:14 | <EvanR> | the last k2 should be k1 of course, typo! not enough coffee |
| 2026-03-03 16:39:06 | × | Googulator46 quits (~Googulato@2a01-036d-0106-0119-2546-5dd3-b1b8-39cd.pool6.digikabel.hu) (Quit: Client closed) |
| 2026-03-03 16:39:30 | → | Googulator46 joins (~Googulato@2a01-036d-0106-0119-2546-5dd3-b1b8-39cd.pool6.digikabel.hu) |
| 2026-03-03 16:40:31 | × | jtnuttall quits (~jeremy@user/jeremyn) (Ping timeout: 264 seconds) |
| 2026-03-03 16:43:04 | → | tmu joins (~tmu@71.227.230.155) |
| 2026-03-03 16:43:38 | <gentauro> | durstloescher: I would highly recommend you to read Okasaki Functional Pearl "Red-Black Trees in a Functional Setting" |
| 2026-03-03 16:43:58 | <gentauro> | I think ACM now is free to read iirc |
| 2026-03-03 16:45:41 | <durstloescher> | thank you all i'll look into the book and try the provided code snippet <3 |
| 2026-03-03 16:46:03 | × | akegalj quits (~akegalj@78-1-128-213.adsl.net.t-com.hr) (Quit: leaving) |
| 2026-03-03 16:46:29 | <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 16:47:15 | <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 16:47:49 | × | acidjnk_new3 quits (~acidjnk@p200300d6e700e523af5c13a8fba9f168.dip0.t-ipconnect.de) (Ping timeout: 245 seconds) |
| 2026-03-03 16:49:52 | <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 16:55:11 | → | jmcantrell_ joins (~weechat@user/jmcantrell) |
| 2026-03-03 16:56:32 | × | durstloescher quits (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) (Quit: My Mac has gone to sleep. ZZZzzz…) |
| 2026-03-03 16:59:10 | <haskellbridge> | <ijouw> Doesn't Set use Red Black trees? |
| 2026-03-03 17:00:17 | <haskellbridge> | <ijouw> Ah, no. |
| 2026-03-03 17:01:55 | → | durstloescher joins (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) |
| 2026-03-03 17:02:16 | <gentauro> | EvanR: deleting in RB-trees is really really complex |
| 2026-03-03 17:03:39 | <haskellbridge> | <ijouw> I cannot remember if I ever had to implement deletion. Will try |
| 2026-03-03 17:04:28 | <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 17:05:25 | <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 17:06:11 | <c_wraith> | (the proof that it's correct is complicated, but the algorithm is simple) |
| 2026-03-03 17:06:26 | × | fgarcia quits (~lei@user/fgarcia) (Ping timeout: 248 seconds) |
| 2026-03-03 17:08:05 | × | wbrawner quits (~wbrawner@129.146.105.153) (Ping timeout: 245 seconds) |
| 2026-03-03 17:10:23 | → | wbrawner joins (~wbrawner@129.146.105.153) |
| 2026-03-03 17:12:52 | <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 17:13:36 | → | chromoblob joins (~chromoblo@user/chromob1ot1c) |
| 2026-03-03 17:22:11 | × | sord937 quits (~sord937@gateway/tor-sasl/sord937) (Quit: sord937) |
| 2026-03-03 17:23:01 | <EvanR> | oof |
| 2026-03-03 17:26:52 | → | n0w0n joins (~john@cpc157419-sotn14-2-0-cust964.15-1.cable.virginm.net) |
| 2026-03-03 17:27:15 | n0w0n | is now known as Guest5338 |
| 2026-03-03 17:31:26 | × | yin quits (~zero@user/zero) (Ping timeout: 252 seconds) |
| 2026-03-03 17:33:45 | → | yin joins (~zero@user/zero) |
| 2026-03-03 17:38:53 | × | madresch quits (~Thunderbi@user/madresch) (Ping timeout: 268 seconds) |
| 2026-03-03 17:39:55 | × | yin quits (~zero@user/zero) (Ping timeout: 264 seconds) |
| 2026-03-03 17:44:22 | → | yin joins (~zero@user/zero) |
| 2026-03-03 17:48:10 | → | jtnuttall joins (~jeremy@user/jeremyn) |
| 2026-03-03 17:50:08 | × | Guest5338 quits (~john@cpc157419-sotn14-2-0-cust964.15-1.cable.virginm.net) (Ping timeout: 252 seconds) |
| 2026-03-03 17:51:55 | × | yin quits (~zero@user/zero) (Ping timeout: 264 seconds) |
| 2026-03-03 17:52:13 | → | u0_a216 joins (~molidae@2401:4900:6289:5b82:f04f:39fd:d52a:6874) |
| 2026-03-03 17:53:30 | × | durstloescher quits (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) (Quit: My Mac has gone to sleep. ZZZzzz…) |
| 2026-03-03 17:54:22 | → | tzh joins (~tzh@c-76-115-131-146.hsd1.or.comcast.net) |
| 2026-03-03 17:55:11 | → | durstloescher joins (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) |
| 2026-03-03 17:55:16 | → | yin joins (~zero@user/zero) |
| 2026-03-03 17:56:24 | × | oskarw quits (~user@user/oskarw) (Remote host closed the connection) |
| 2026-03-03 17:56:34 | × | Square2 quits (~Square4@user/square) (Ping timeout: 245 seconds) |
| 2026-03-03 17:57:48 | <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:00:47 | × | durstloescher quits (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) (Quit: My Mac has gone to sleep. ZZZzzz…) |
| 2026-03-03 18:05:30 | <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 18:05:33 | → | Square2 joins (~Square4@user/square) |
| 2026-03-03 18:07:16 | × | tromp quits (~textual@2001:1c00:3487:1b00:bca6:b25a:741d:ca28) (Quit: My iMac has gone to sleep. ZZZzzz…) |
| 2026-03-03 18:10:18 | <c_wraith> | absolutely the best lesson to take from that, yes |
| 2026-03-03 18:10:42 | × | merijn quits (~merijn@77.242.116.146) (Ping timeout: 246 seconds) |
| 2026-03-03 18:11:22 | → | durstloescher joins (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) |
| 2026-03-03 18:24:24 | → | skinkitten joins (~skinkitte@user/skinkitten) |
| 2026-03-03 18:26:22 | × | vanishingideal quits (~vanishing@user/vanishingideal) (Ping timeout: 268 seconds) |
| 2026-03-03 18:28:04 | → | CiaoSen joins (~Jura@2a02:8071:64e1:da0:5a47:caff:fe78:33db) |
| 2026-03-03 18:31:46 | × | jtnuttall quits (~jeremy@user/jeremyn) (Ping timeout: 248 seconds) |
| 2026-03-03 18:32:19 | → | tromp joins (~textual@2001:1c00:3487:1b00:bca6:b25a:741d:ca28) |
| 2026-03-03 18:32:28 | → | Square joins (~Square@user/square) |
| 2026-03-03 18:34:30 | × | Square2 quits (~Square4@user/square) (Ping timeout: 246 seconds) |
| 2026-03-03 18:45:35 | × | wbrawner quits (~wbrawner@129.146.105.153) (Ping timeout: 245 seconds) |
| 2026-03-03 18:46:27 | → | target_i joins (~target_i@user/target-i/x-6023099) |
| 2026-03-03 18:49:13 | → | wbrawner joins (~wbrawner@129.146.105.153) |
| 2026-03-03 18:49:57 | → | merijn joins (~merijn@host-cl.cgnat-g.v4.dfn.nl) |
| 2026-03-03 18:54:37 | × | euphores quits (~SASL_euph@user/euphores) (Quit: Leaving.) |
| 2026-03-03 18:57:19 | × | wbrawner quits (~wbrawner@129.146.105.153) (Ping timeout: 264 seconds) |
| 2026-03-03 18:59:38 | × | durstloescher quits (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) (Quit: My Mac has gone to sleep. ZZZzzz…) |
| 2026-03-03 19:02:40 | × | merijn quits (~merijn@host-cl.cgnat-g.v4.dfn.nl) (Ping timeout: 245 seconds) |
| 2026-03-03 19:03:21 | → | durstloescher joins (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) |
| 2026-03-03 19:05:35 | × | durstloescher quits (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) (Client Quit) |
| 2026-03-03 19:08:46 | → | arandombit joins (~arandombi@2a02:2455:8656:7100:159d:62bb:2d29:74f6) |
| 2026-03-03 19:08:46 | × | arandombit quits (~arandombi@2a02:2455:8656:7100:159d:62bb:2d29:74f6) (Changing host) |
| 2026-03-03 19:08:46 | → | arandombit joins (~arandombi@user/arandombit) |
| 2026-03-03 19:12:57 | × | EvanR quits (~EvanR@user/evanr) (Remote host closed the connection) |
| 2026-03-03 19:13:17 | → | EvanR joins (~EvanR@user/evanr) |
| 2026-03-03 19:14:09 | → | merijn joins (~merijn@host-cl.cgnat-g.v4.dfn.nl) |
| 2026-03-03 19:15:26 | → | wbrawner joins (~wbrawner@129.146.105.153) |
| 2026-03-03 19:16:23 | × | terrorjack quits (~terrorjac@2a01:4f8:271:2d98::2) (Quit: The Lounge - https://thelounge.chat) |
| 2026-03-03 19:17:18 | → | mange joins (~mange@user/mange) |
| 2026-03-03 19:17:32 | × | Square quits (~Square@user/square) (Remote host closed the connection) |
| 2026-03-03 19:19:14 | × | merijn quits (~merijn@host-cl.cgnat-g.v4.dfn.nl) (Ping timeout: 248 seconds) |
| 2026-03-03 19:19:17 | → | ajdev joins (~ajdev@2001:1c04:3024:c500:177a:3bd7:e2fe:fbc5) |
| 2026-03-03 19:20:13 | → | durstloescher joins (~textual@ip4d16b23b.dynamic.kabel-deutschland.de) |
| 2026-03-03 19:20:24 | → | Square joins (~Square@user/square) |
All times are in UTC.