Logs: liberachat/#haskell
| 2025-09-20 09:14:53 | <Enrico63> | Ok, yes, I see that. I think I just haven't been clear about what is puzzling me. |
| 2025-09-20 09:16:03 | trickard__ | is now known as trickard |
| 2025-09-20 09:16:50 | <tomsmeding> | what is puzzling you? :) |
| 2025-09-20 09:18:17 | <mauke> | the nature of your game |
| 2025-09-20 09:18:19 | <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 09:18:48 | <Enrico63> | I see your point of mutability being an impl. detail, yes. But: |
| 2025-09-20 09:19:24 | × | ZLima12 quits (~zlima12@user/meow/ZLima12) (Remote host closed the connection) |
| 2025-09-20 09:20:16 | <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 09:20:31 | <tomsmeding> | right |
| 2025-09-20 09:21:01 | <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 09:21:01 | → | ZLima12 joins (~zlima12@user/meow/ZLima12) |
| 2025-09-20 09:21:17 | <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 09:21:49 | <tomsmeding> | right. It depends mostly on what you consider your "base language" of pure operations |
| 2025-09-20 09:22:22 | <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 09:22:41 | <tomsmeding> | but it makes a lot of sense to consider this a pure operation, so we include this, black-box, as a pure operation in our "base language" |
| 2025-09-20 09:23:02 | <tomsmeding> | similarly instead of writing zeros, writing elements computed using a pure function is still pure |
| 2025-09-20 09:23:26 | <tomsmeding> | ( https://hackage.haskell.org/package/vector-0.13.1.0/docs/Data-Vector.html#v:generate ) |
| 2025-09-20 09:23:43 | <tomsmeding> | but somehow it feels wrong for `array` to also be a pure function in our "base language" |
| 2025-09-20 09:23:45 | <tomsmeding> | why is that? |
| 2025-09-20 09:23:50 | <Enrico63> | Maybe I'm just making confusion between language features and space requirements of an algo, now that I think more about it? |
| 2025-09-20 09:24:06 | <tomsmeding> | no I completely get your feeling, I feel the same way about `array` |
| 2025-09-20 09:24:12 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-09-20 09:24:17 | <tomsmeding> | but I do also think that it's a question of perspective |
| 2025-09-20 09:24:59 | <tomsmeding> | maybe it's that `array` does not naturally parallelise? |
| 2025-09-20 09:25:26 | <tomsmeding> | but it does -- you need an atomic write operation for the elements in case of overlap, but otherwise you're good |
| 2025-09-20 09:25:58 | <Enrico63> | What I mean is that backward permutation, from a purely algorithmic perspective, probably requires O(n) space in order to achieve O(n) time. And O(n) space I think assumes that you have O(1) cost for reading-writing anywhere... |
| 2025-09-20 09:26:20 | <tomsmeding> | backward permutation is the "easy" one |
| 2025-09-20 09:26:33 | <Enrico63> | oh, sorry, then s/back/for/g |
| 2025-09-20 09:26:35 | <tomsmeding> | right |
| 2025-09-20 09:26:54 | <tomsmeding> | what O(n) space is that? The destination array? |
| 2025-09-20 09:26:59 | <Enrico63> | yeah |
| 2025-09-20 09:26:59 | <tomsmeding> | you need that anyway |
| 2025-09-20 09:27:10 | <tomsmeding> | apart from inputs and outputs, no additional space is needed |
| 2025-09-20 09:27:24 | <tomsmeding> | backward permutation (the easy one) also needs space for the input _and_ the output |
| 2025-09-20 09:27:31 | <tomsmeding> | can't be done in-place either |
| 2025-09-20 09:27:43 | <tomsmeding> | (even if input and output happen to be the same size) |
| 2025-09-20 09:28:53 | <Enrico63> | What you mean? Any permutation can be done in-place if you can swap elements, no? |
| 2025-09-20 09:28:54 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 260 seconds) |
| 2025-09-20 09:29:03 | <tomsmeding> | from my perspective, the thing that makes `array`/`accumArray` (the forward permutation thing) feel "different" is that we tacitly accept a pull array (Data.Vector.generate) as a basic pure operation, but little more |
| 2025-09-20 09:29:14 | × | qqe quits (~qqq@185.54.23.100) (Remote host closed the connection) |
| 2025-09-20 09:29:16 | → | chexum_ joins (~quassel@gateway/tor-sasl/chexum) |
| 2025-09-20 09:29:20 | × | chexum quits (~quassel@gateway/tor-sasl/chexum) (Ping timeout: 272 seconds) |
| 2025-09-20 09:29:30 | <tomsmeding> | Enrico63: how are you going to do a bijective backward permutation in O(n) time in-place? |
| 2025-09-20 09:29:56 | <Enrico63> | Oh, I was lifting the O(n) req |
| 2025-09-20 09:30:08 | <tomsmeding> | okay remove the "in O(n) time" then lol |
| 2025-09-20 09:30:21 | <Enrico63> | As in, I thought you were saying something general |
| 2025-09-20 09:30:25 | <Enrico63> | silly of me thinking so :D |
| 2025-09-20 09:30:40 | <tomsmeding> | well, I think of these data movement operations as having a certain expected time complexity |
| 2025-09-20 09:30:50 | <tomsmeding> | but in this particular case the time complexity is, I think, irrelevant to my point :p |
| 2025-09-20 09:31:09 | <tomsmeding> | I know of a way to do a bijective backward permutation in-place, but it's very sequential and mutation-heavy |
| 2025-09-20 09:31:22 | × | Enrico63 quits (~Enrico63@2a0b:e541:10d0:0:9efc:e8ff:fe24:3213) (Quit: Client closed) |
| 2025-09-20 09:31:36 | → | Enrico63 joins (~Enrico63@2a0b:e541:10d0:0:9efc:e8ff:fe24:3213) |
| 2025-09-20 09:31:59 | <tomsmeding> | and moreover, that sequential, mutation-heavy algorithm for a bijective backward permutation can be rather easily modified to do a bijective forward permutation instead |
| 2025-09-20 09:32:37 | <tomsmeding> | it's when you lift the requirement of being in-place that the two start to meaningfully differ, as far as I know -- though I may be wrong here, because I've thought very little about the in-place case |
| 2025-09-20 09:32:51 | <tomsmeding> | (if you need history: https://ircbrowse.tomsmeding.com/browse/lchaskell?events_page=16546 ) |
| 2025-09-20 09:33:05 | × | fgarcia quits (~lei@user/fgarcia) (Remote host closed the connection) |
| 2025-09-20 09:34:30 | <tomsmeding> | I guess what I'm saying is: do you have a _precise_ way in which forward permutation is "less pure" (for some suitable definition of "less pure" that you can choose) than backward permutation? |
| 2025-09-20 09:35:07 | → | qqe joins (~qqq@185.54.23.100) |
| 2025-09-20 09:36:18 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-09-20 09:36:34 | → | Tuplanolla joins (~Tuplanoll@91-159-187-167.elisa-laajakaista.fi) |
| 2025-09-20 09:37:56 | → | ljdarj1 joins (~Thunderbi@user/ljdarj) |
| 2025-09-20 09:41:07 | × | ljdarj quits (~Thunderbi@user/ljdarj) (Ping timeout: 244 seconds) |
| 2025-09-20 09:41:07 | ljdarj1 | is now known as ljdarj |
| 2025-09-20 09:41:09 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 260 seconds) |
| 2025-09-20 09:41:19 | × | craunts79 quits (~craunts@152.32.99.194) (Quit: The Lounge - https://thelounge.chat) |
| 2025-09-20 09:41:42 | <Enrico63> | Yes, the way I see it. The solution `permute idxs list = let arr = listArray (0, length list - 1) list in map (arr !) idxs` is fast by being able to read with random access. The ouptut is produced purely, by picking elements from arr while building the new output list. The solution `elems (array (0, n-1) (zip idxs list))` produces the output my |
| 2025-09-20 09:41:42 | <Enrico63> | creating the array all at once, and then mutating the elements with random access. |
| 2025-09-20 09:42:04 | <Enrico63> | That's probably not _precise_, but I see a difference between the two :D |
| 2025-09-20 09:44:36 | <Enrico63> | I see that `listArray (0, lenth list - 1) list` is probably using mutability the same way that `array (0, n-1) (zip idx list))` is using it :/ |
| 2025-09-20 09:45:20 | <Enrico63> | well, maybe that's why the two things are not so different :/ |
| 2025-09-20 09:45:55 | → | fgarcia joins (~lei@user/fgarcia) |
| 2025-09-20 09:46:05 | <tomsmeding> | Enrico63: your reasoning why `elems (array (0, n-1) (zip idxs list))` is not pure first splits up `array` in two phases: array allocation and then a bunch of writes |
| 2025-09-20 09:46:11 | <tomsmeding> | why do you not split up `listArray` similarly? |
| 2025-09-20 09:46:26 | <tomsmeding> | right |
| 2025-09-20 09:46:48 | <Enrico63> | yeah, I see |
| 2025-09-20 09:46:49 | <tomsmeding> | I know they feel different, but indeed the point I'm making is that in terms of _purity_, they aren't necessarily so different |
| 2025-09-20 09:47:22 | <tomsmeding> | they generalise differently to non-bijective index mapping functions, and they parallelise somewhat differently, especially in the non-bijective case |
| 2025-09-20 09:47:43 | <tomsmeding> | but I don't think there's a robust way you can argue that one is more pure than the other |
| 2025-09-20 09:48:01 | <tomsmeding> | without picking an arbitrary "base language" of pure operations that you allow |
| 2025-09-20 09:49:16 | <tomsmeding> | also, they're just algorithmically not the same |
| 2025-09-20 09:49:48 | <tomsmeding> | but "not the same" doesn't imply an order of preference |
| 2025-09-20 09:50:20 | <Enrico63> | Thanks for the discussion! :) |
| 2025-09-20 09:50:29 | <tomsmeding> | relevant: https://hackage-content.haskell.org/package/massiv-1.0.5.0/docs/Data-Massiv-Array.html (the `D` representation is a pull array, represented as effectively (Int, Int -> a); the `DL` representation is a push array) |
| 2025-09-20 09:50:42 | <Enrico63> | Now that I'm unemployed, I have plenty of time to discuss stuff, ahah |
| 2025-09-20 09:50:44 | <tomsmeding> | pull arrays are generally more versatile |
| 2025-09-20 09:50:58 | <tomsmeding> | they behave more intuitively under composition of pull-style functions |
| 2025-09-20 09:51:39 | × | fgarcia quits (~lei@user/fgarcia) (Ping timeout: 260 seconds) |
| 2025-09-20 09:51:42 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-09-20 09:54:03 | → | fgarcia joins (~lei@user/fgarcia) |
| 2025-09-20 09:55:11 | × | puke quits (~puke@user/puke) (Read error: Connection reset by peer) |
| 2025-09-20 09:55:31 | → | puke joins (~puke@user/puke) |
| 2025-09-20 09:56:19 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 260 seconds) |
| 2025-09-20 09:56:54 | × | fgarcia quits (~lei@user/fgarcia) (Max SendQ exceeded) |
| 2025-09-20 09:59:43 | × | ljdarj quits (~Thunderbi@user/ljdarj) (Ping timeout: 244 seconds) |
| 2025-09-20 10:00:24 | → | __monty__ joins (~toonn@user/toonn) |
| 2025-09-20 10:00:43 | → | ljdarj joins (~Thunderbi@user/ljdarj) |
| 2025-09-20 10:07:08 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-09-20 10:11:34 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 258 seconds) |
| 2025-09-20 10:11:53 | × | Square2 quits (~Square@user/square) (Remote host closed the connection) |
| 2025-09-20 10:12:18 | → | Square2 joins (~Square@user/square) |
All times are in UTC.