Newest at the top
2024-10-06 19:40:16 +0200 | morb | (~morb@pool-108-41-100-120.nycmny.fios.verizon.net) (Read error: Connection reset by peer) |
2024-10-06 19:40:13 +0200 | <int-e> | well, vector has O(1) uncons :P |
2024-10-06 19:38:41 +0200 | merijn | (~merijn@204-220-045-062.dynamic.caiway.nl) merijn |
2024-10-06 19:37:02 +0200 | ljdarj | (~Thunderbi@user/ljdarj) ljdarj |
2024-10-06 19:36:06 +0200 | morb | (~morb@pool-108-41-100-120.nycmny.fios.verizon.net) |
2024-10-06 19:35:41 +0200 | vanishingideal | (~vanishing@user/vanishingideal) vanishingideal |
2024-10-06 19:34:07 +0200 | <Inst> | you'd imagine they'd just use a bidirectional dynamic vector to appeal to their userbase |
2024-10-06 19:34:02 +0200 | <Franciman> | davean: i see many thanks |
2024-10-06 19:33:55 +0200 | vanishingideal | (~vanishing@user/vanishingideal) (Ping timeout: 252 seconds) |
2024-10-06 19:33:45 +0200 | <Inst> | Python seems to have that as well |
2024-10-06 19:33:36 +0200 | <Franciman> | i don't know it |
2024-10-06 19:33:34 +0200 | <Inst> | EczemaScript ;) |
2024-10-06 19:33:28 +0200 | <Inst> | Javascript |
2024-10-06 19:33:28 +0200 | <int-e> | ECMAScript |
2024-10-06 19:33:22 +0200 | <Franciman> | what is JS, Inst ? |
2024-10-06 19:33:18 +0200 | lxsameer | (~lxsameer@Serene/lxsameer) (Ping timeout: 272 seconds) |
2024-10-06 19:33:15 +0200 | <Inst> | what's the tradeoff of bidirectional vs unidirectional dynamic arrays / lists / vectors? |
2024-10-06 19:33:01 +0200 | <Inst> | i'm curious, even JS has O(n) on shift |
2024-10-06 19:32:54 +0200 | <int-e> | And this sidesteps many of the usual uses of dynamic vectors. |
2024-10-06 19:32:24 +0200 | <int-e> | But that's the thing... we want stay outside of IO/ST for as much as possible. And we have all these fusion frameworks which let us work with things like lists-as-mutable-vectors and often get good performance because they never actually materialize. |
2024-10-06 19:30:36 +0200 | <davean> | not mutable vector, which is the only thing we have thats vector like. |
2024-10-06 19:30:10 +0200 | <int-e> | right. vector is far worse for mutations :P |
2024-10-06 19:28:52 +0200 | <davean> | Sequence is WAY off vector performance. |
2024-10-06 19:28:49 +0200 | <Inst> | hmmm, you can just newtype vector for dynamic vectors, you don't need any additional information in order to implement a dynamic vector |
2024-10-06 19:28:45 +0200 | athan | (~athan@syn-098-153-145-140.biz.spectrum.com) (Quit: Konversation terminated!) |
2024-10-06 19:27:45 +0200 | merijn | (~merijn@204-220-045-062.dynamic.caiway.nl) (Ping timeout: 248 seconds) |
2024-10-06 19:25:55 +0200 | <int-e> | (Even when you consider amortized cost, persistence is a big obstacle to combining arrays and mutation. Okasaki-like tricks will work.) |
2024-10-06 19:25:06 +0200 | <Inst> | Sequence is built on fingertrees |
2024-10-06 19:24:21 +0200 | <int-e> | of course not |
2024-10-06 19:22:10 +0200 | <Inst> | yeah but iirc it's not based on bytearray, right? |
2024-10-06 19:21:59 +0200 | <int-e> | Data.Seq is a thing too |
2024-10-06 19:21:48 +0200 | <Inst> | davean: you can define a bidirectional dynamic vector, amortized O(1) cons |
2024-10-06 19:21:35 +0200 | <davean> | You can sorta get close amortised, but that requires reusing memory |
2024-10-06 19:21:09 +0200 | <Rembane> | Inst: Are you thinking of Data.Vector? |
2024-10-06 19:21:06 +0200 | <davean> | ... you can't have O(1) cons |
2024-10-06 19:20:54 +0200 | merijn | (~merijn@204-220-045-062.dynamic.caiway.nl) merijn |
2024-10-06 19:20:43 +0200 | <Inst> | iirc the newbie rule of thumb is "prefer vectors unless you need laziness", but vector doesn't have O(1) cons |
2024-10-06 19:20:24 +0200 | <Inst> | btw, why doesn't Haskell have dynamic vectors? |
2024-10-06 19:19:09 +0200 | <Rembane> | davean: Oh. That sounds way too hard. |
2024-10-06 19:18:57 +0200 | <davean> | Rembane: Some of the best Haskellers I know tries that, and as a team failed. |
2024-10-06 19:18:48 +0200 | <Rembane> | davean: ^^ |
2024-10-06 19:18:23 +0200 | <dolio> | So, like, maybe you could use linear types to design some methodology of using unsafe operations, and very carefully implement something on top of the unsafe operations that provided some kind of typical performance increase. But the linearity stuff is not inherently doing the things that perform better in known ways. |
2024-10-06 19:18:23 +0200 | <davean> | HAVE FUN! |
2024-10-06 19:18:21 +0200 | <davean> | Rembane: Try writing like just a merge step of a merge sort with liner types, consider the edge cases. |
2024-10-06 19:13:48 +0200 | ash3en | (~Thunderbi@2a03:7846:b6eb:101:93ac:a90a:da67:f207) ash3en |
2024-10-06 19:13:21 +0200 | merijn | (~merijn@204-220-045-062.dynamic.caiway.nl) (Ping timeout: 248 seconds) |
2024-10-06 19:13:07 +0200 | <dolio> | I haven't looked closely, but the problem seems to be that it wasn't designed to address the usual, known uses of linear types. |
2024-10-06 19:12:49 +0200 | <Rembane> | davean: Got it! |
2024-10-06 19:11:39 +0200 | <davean> | Rembane: broken? No. The source of the issues using it? Yes |
2024-10-06 19:11:09 +0200 | <Rembane> | davean: Do you imply that the theory is broken? Or have I misunderstood you? |