2025/09/20

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 +0200ZLima12(~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 +0200ZLima12(~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 +0200trickard__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 +0200merijn(~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 +0200merijn(~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.