Newest at the top
2025-09-20 11:22:22 +0200 | <tomsmeding> | allocating an array incurs mutation: you mutate the memory allocator's internal data structures and write a bunch of zeros to memory |
2025-09-20 11:21:49 +0200 | <tomsmeding> | right. It depends mostly on what you consider your "base language" of pure operations |
2025-09-20 11:21:17 +0200 | <tomsmeding> | (in the usual RAM model where memory access is considered O(1), ignoring physical effects that mean memory access is more accurately something like O(sqrt(n)) with a very low constant factor) |
2025-09-20 11:21:01 +0200 | ZLima12 | (~zlima12@user/meow/ZLima12) ZLima12 |
2025-09-20 11:21:01 +0200 | <Enrico63> | Mutation might be an impl. detail, but it kind leaks out by just knowing the complexity of the algo. If it's O(n), you know it's doing mutability. |
2025-09-20 11:20:31 +0200 | <tomsmeding> | right |
2025-09-20 11:20:16 +0200 | <Enrico63> | If I see something like `elems (array (0, n-1) (zip idxs list))`, and one tells me it's happening in O(n), ... then I know that array is allocating an array, doing mutation of that very array, and the passing that very array to elems. |
2025-09-20 11:19:24 +0200 | ZLima12 | (~zlima12@user/meow/ZLima12) (Remote host closed the connection) |
2025-09-20 11:18:48 +0200 | <Enrico63> | I see your point of mutability being an impl. detail, yes. But: |
2025-09-20 11:18:19 +0200 | <Enrico63> | I guess what I'm saying is that with the example I gave above, I understand that the problem of (backward) permutation is not doable in O(n) unless you have O(1) random access + mutability. And I'd like to understand a bit more about the relation between complexity and .. language features? |
2025-09-20 11:18:17 +0200 | <mauke> | the nature of your game |
2025-09-20 11:16:50 +0200 | <tomsmeding> | what is puzzling you? :) |
2025-09-20 11:16:03 +0200 | trickard__ | trickard |
2025-09-20 11:14:53 +0200 | <Enrico63> | Ok, yes, I see that. I think I just haven't been clear about what is puzzling me. |
2025-09-20 11:14:20 +0200 | <tomsmeding> | nice |
2025-09-20 11:14:17 +0200 | <lambdabot> | [0 + a + b + c,0,0 + d,0] |
2025-09-20 11:14:15 +0200 | <tomsmeding> | > A.elems $ A.accumArray (+) 0 (0,3) (zip [0,0,0,2] [a,b,c,d]) |
2025-09-20 11:14:06 +0200 | <lambdabot> | Defined. |
2025-09-20 11:14:05 +0200 | <tomsmeding> | @let import qualified Data.Array as A |
2025-09-20 11:13:33 +0200 | <tomsmeding> | (1+2+3 = 6) |
2025-09-20 11:13:18 +0200 | merijn | (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 258 seconds) |
2025-09-20 11:13:11 +0200 | <tomsmeding> | if the permutation is bijective, i.e. you have no overlap, no monoid is required, as you've seen |
2025-09-20 11:12:52 +0200 | <tomsmeding> | this is a forward permutation with idxs=[0,0,0,2] and list=[1,2,3,4], using the (0, +) monoid |
2025-09-20 11:12:24 +0200 | <yahb2> | [6,0,4,0] |
2025-09-20 11:12:24 +0200 | <tomsmeding> | % A.elems $ A.accumArray (+) 0 (0,3) (zip [0,0,0,2] [1,2,3,4]) |
2025-09-20 11:12:18 +0200 | <yahb2> | array (0,3) [(0,6),(1,0),(2,4),(3,0)] |
2025-09-20 11:12:18 +0200 | <tomsmeding> | % A.accumArray (+) 0 (0,3) (zip [0,0,0,2] [1,2,3,4]) |
2025-09-20 11:11:59 +0200 | <Enrico63> | You're executing Haskell code in here... :O |
2025-09-20 11:11:41 +0200 | <yahb2> | <no output> |
2025-09-20 11:11:41 +0200 | <tomsmeding> | % import qualified Data.Array as A |
2025-09-20 11:11:26 +0200 | <tomsmeding> | works fine |
2025-09-20 11:11:23 +0200 | <yahb2> | "hhhs" |
2025-09-20 11:11:23 +0200 | <tomsmeding> | % backpermute [0,0,0,2] "hask" |
2025-09-20 11:11:17 +0200 | <yahb2> | <no output> |
2025-09-20 11:11:17 +0200 | <tomsmeding> | % backpermute idxs list = map (list !!) idxs |
2025-09-20 11:11:04 +0200 | <tomsmeding> | generalising forward permutation suddenly requires a combining function |
2025-09-20 11:10:57 +0200 | <tomsmeding> | well, we can easily generalise backward permutation to allow that |
2025-09-20 11:10:50 +0200 | <tomsmeding> | but we can generalise the operation to allow that |
2025-09-20 11:10:41 +0200 | <Enrico63> | Why mutiple elements sent to the same spot? That doesn't happen with permutation.. |
2025-09-20 11:09:36 +0200 | <tomsmeding> | this is why Data.Array.accumArray has a combining function |
2025-09-20 11:09:18 +0200 | <tomsmeding> | how do you combine multiple elements being sent to the same spot? |
2025-09-20 11:09:09 +0200 | <tomsmeding> | sending multiple source elements to the same destination element using `permute` is suddenly very interesting |
2025-09-20 11:08:49 +0200 | merijn | (~merijn@host-vr.cgnat-g.v4.dfn.nl) merijn |
2025-09-20 11:08:41 +0200 | <tomsmeding> | having multiple destination elements read from the same source element is... just do that |
2025-09-20 11:08:12 +0200 | <Enrico63> | I'm not sure either, ahahah |
2025-09-20 11:08:12 +0200 | <tomsmeding> | backward permutation is also easier to parallelise efficiently than forward permutation, especially if the permutation is not required to be bijective |
2025-09-20 11:07:42 +0200 | <Enrico63> | Oh, right, didn't read that. Anyway, that's why I say it's a non-problem |
2025-09-20 11:07:39 +0200 | <tomsmeding> | I'm not sure what kind of theory you're looking for :p |
2025-09-20 11:07:20 +0200 | <tomsmeding> | yes, and that's what I did using listArray |
2025-09-20 11:07:03 +0200 | <Enrico63> | Ok, but backward permutation is a non-problem. I mean, if your original snippet can be even O(n) if `list` gives O(1) `!!`, and requires no mutability to be that fast. |