Logs: liberachat/#haskell
| 2025-09-20 07:32:42 | → | rvalue- joins (~rvalue@about/hackers/rvalue) |
| 2025-09-20 07:32:49 | × | rvalue quits (~rvalue@about/hackers/rvalue) (Ping timeout: 260 seconds) |
| 2025-09-20 07:34:17 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-09-20 07:35:31 | rvalue- | is now known as rvalue |
| 2025-09-20 07:38:51 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 256 seconds) |
| 2025-09-20 07:39:21 | → | ljdarj joins (~Thunderbi@user/ljdarj) |
| 2025-09-20 07:45:27 | → | mreh joins (~matthew@host86-146-25-35.range86-146.btcentralplus.com) |
| 2025-09-20 07:48:09 | → | wootehfoot joins (~wootehfoo@user/wootehfoot) |
| 2025-09-20 07:48:46 | × | weary-traveler quits (~user@user/user363627) (Remote host closed the connection) |
| 2025-09-20 07:49:42 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-09-20 07:54:20 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 258 seconds) |
| 2025-09-20 07:55:48 | × | Lord_of_Life quits (~Lord@user/lord-of-life/x-2819915) (Quit: Laa shay'a waqi'un moutlaq bale kouloun moumkine) |
| 2025-09-20 07:56:43 | → | Lord_of_Life joins (~Lord@user/lord-of-life/x-2819915) |
| 2025-09-20 08:05:09 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-09-20 08:10:09 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 260 seconds) |
| 2025-09-20 08:18:32 | → | Axman7217 joins (~Axman6@user/axman6) |
| 2025-09-20 08:18:41 | × | tromp quits (~textual@2001:1c00:3487:1b00:5948:8c6b:93fe:bd0a) (Quit: My iMac has gone to sleep. ZZZzzz…) |
| 2025-09-20 08:20:32 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-09-20 08:20:33 | × | Axman6 quits (~Axman6@user/axman6) (Ping timeout: 240 seconds) |
| 2025-09-20 08:25:19 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 260 seconds) |
| 2025-09-20 08:29:45 | → | Square2 joins (~Square@user/square) |
| 2025-09-20 08:30:03 | × | Googulator1 quits (~Googulato@2a01-036d-0106-217b-d921-1fcb-7b52-cdbe.pool6.digikabel.hu) (Ping timeout: 250 seconds) |
| 2025-09-20 08:35:17 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-09-20 08:41:06 | → | Enrico63 joins (~Enrico63@2a0b:e541:10d0:0:9efc:e8ff:fe24:3213) |
| 2025-09-20 08:42:14 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 260 seconds) |
| 2025-09-20 08:44:50 | × | Sgeo__ quits (~Sgeo@user/sgeo) (Read error: Connection reset by peer) |
| 2025-09-20 08:47:03 | <Enrico63> | Hello there! |
| 2025-09-20 08:50:24 | <Rembane> | Hello Enrico63 ! |
| 2025-09-20 08:50:57 | → | acidjnk joins (~acidjnk@p200300d6e717196005b97722411e3ede.dip0.t-ipconnect.de) |
| 2025-09-20 08:53:20 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-09-20 08:57:16 | <Enrico63> | I'm going though https://haskell.mooc.fi/part2 and one exercise (https://github.com/moocfi/haskell-mooc/blob/59735e76d37c5470504be4d64206cd49660e1324/exercises/Set9a.hs#L187-L229) consists in implementing a permutation function that works like this: |
| 2025-09-20 08:57:17 | <Enrico63> | -- permute [0,1,2,3] "hask" ==> "hask" |
| 2025-09-20 08:57:17 | <Enrico63> | -- permute [2,0,1,3] "hask" ==> "ashk" |
| 2025-09-20 08:57:18 | <Enrico63> | -- permute [1,2,3,0] "hask" ==> "khas" |
| 2025-09-20 08:57:18 | <Enrico63> | Using just lists, I've come up with this solution, which takes O(n log n - i.e. complexity of sorting): |
| 2025-09-20 08:57:19 | <Enrico63> | permute :: [Int] -> [a] -> [a] |
| 2025-09-20 08:57:19 | <Enrico63> | permute p s = map snd $ sortOn fst $ zip p s |
| 2025-09-20 08:57:20 | <Enrico63> | however, if I had used mutable arrays, I could have done something like this, which is just O(n), right? |
| 2025-09-20 08:57:20 | <Enrico63> | permute :: [Int] -> [a] -> [a] |
| 2025-09-20 08:57:21 | <Enrico63> | permute idxs list = |
| 2025-09-20 08:57:21 | <Enrico63> | elems (array (0, n-1) (zip idxs list)) |
| 2025-09-20 08:57:22 | <Enrico63> | where n = length list |
| 2025-09-20 08:57:22 | <Enrico63> | To me it feels like such a solution requires 2 features: the ability to random access an array with O(1), and mutability. |
| 2025-09-20 08:57:23 | <Enrico63> | The solution with sorting doesn't use either of those and indeed it pays with O(n log n) or whatever. |
| 2025-09-20 08:57:23 | <Enrico63> | Can anybody suggest some material I could refer to, if I want to better understand the stuff above? |
| 2025-09-20 08:57:58 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 258 seconds) |
| 2025-09-20 08:58:48 | opqdonut | is now known as opqdonut__ |
| 2025-09-20 08:58:57 | opqdonut_ | is now known as opqdonut |
| 2025-09-20 08:59:49 | <tomsmeding> | Enrico63: the array you used isn't mutable, and doesn't need to be |
| 2025-09-20 09:00:35 | <tomsmeding> | I would say that the most straightforward solution is the O(n^2) `permute idxs list = map (list !!) idxs` |
| 2025-09-20 09:01:21 | <tomsmeding> | which you can speed up with an array using `permute idxs list = let arr = listArray (0, length list - 1) list in map (arr !) idxs` |
| 2025-09-20 09:01:58 | <tomsmeding> | ... apologies, I got the permutation in the wrong direction |
| 2025-09-20 09:02:06 | <tomsmeding> | your `array` solution is indeed correct, my suggestions are not |
| 2025-09-20 09:02:33 | <tomsmeding> | `array` is indeed implemented using mutation under the hood, but the function as a whole is pure |
| 2025-09-20 09:03:06 | <tomsmeding> | and indeed, all of haskell is, necessarily: the underlying hardware can do things only through mutation |
| 2025-09-20 09:03:16 | <Enrico63> | Yeah, I know that. But the reason why it is fast is that it uses mutation. |
| 2025-09-20 09:03:31 | <tomsmeding> | to an extent |
| 2025-09-20 09:03:48 | <tomsmeding> | one thing you could I guess look up in reference to this, is pull arrays vs push arrays |
| 2025-09-20 09:03:54 | <Enrico63> | So my question is not about Haskell. It's just that doing this in Haskell forced me to think about something I hadn't thought before. |
| 2025-09-20 09:04:09 | <tomsmeding> | what you're being asked here is a forward permutation, which you can do efficiently in push-array style and not in pull-array style |
| 2025-09-20 09:04:46 | <tomsmeding> | a backward permutation (which is what I described with `map (list !!) idxs`) can be efficiently implemented using pull arrays, which is more natural in a functional setting |
| 2025-09-20 09:04:49 | <Enrico63> | Forward permutation =? I have the list of destination indices of original indices 0,1,2,..? |
| 2025-09-20 09:05:12 | <Enrico63> | Ok, I think that's what you mean by forward/backward permutation |
| 2025-09-20 09:05:14 | <tomsmeding> | yes |
| 2025-09-20 09:07:03 | <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. |
| 2025-09-20 09:07:20 | <tomsmeding> | yes, and that's what I did using listArray |
| 2025-09-20 09:07:39 | <tomsmeding> | I'm not sure what kind of theory you're looking for :p |
| 2025-09-20 09:07:42 | <Enrico63> | Oh, right, didn't read that. Anyway, that's why I say it's a non-problem |
| 2025-09-20 09:08:12 | <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 09:08:12 | <Enrico63> | I'm not sure either, ahahah |
| 2025-09-20 09:08:41 | <tomsmeding> | having multiple destination elements read from the same source element is... just do that |
| 2025-09-20 09:08:49 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-09-20 09:09:09 | <tomsmeding> | sending multiple source elements to the same destination element using `permute` is suddenly very interesting |
| 2025-09-20 09:09:18 | <tomsmeding> | how do you combine multiple elements being sent to the same spot? |
| 2025-09-20 09:09:36 | <tomsmeding> | this is why Data.Array.accumArray has a combining function |
| 2025-09-20 09:10:41 | <Enrico63> | Why mutiple elements sent to the same spot? That doesn't happen with permutation.. |
| 2025-09-20 09:10:50 | <tomsmeding> | but we can generalise the operation to allow that |
| 2025-09-20 09:10:57 | <tomsmeding> | well, we can easily generalise backward permutation to allow that |
| 2025-09-20 09:11:04 | <tomsmeding> | generalising forward permutation suddenly requires a combining function |
| 2025-09-20 09:11:17 | <tomsmeding> | % backpermute idxs list = map (list !!) idxs |
| 2025-09-20 09:11:17 | <yahb2> | <no output> |
| 2025-09-20 09:11:23 | <tomsmeding> | % backpermute [0,0,0,2] "hask" |
| 2025-09-20 09:11:23 | <yahb2> | "hhhs" |
| 2025-09-20 09:11:26 | <tomsmeding> | works fine |
| 2025-09-20 09:11:41 | <tomsmeding> | % import qualified Data.Array as A |
| 2025-09-20 09:11:41 | <yahb2> | <no output> |
| 2025-09-20 09:11:59 | <Enrico63> | You're executing Haskell code in here... :O |
| 2025-09-20 09:12:18 | <tomsmeding> | % A.accumArray (+) 0 (0,3) (zip [0,0,0,2] [1,2,3,4]) |
| 2025-09-20 09:12:18 | <yahb2> | array (0,3) [(0,6),(1,0),(2,4),(3,0)] |
| 2025-09-20 09:12:24 | <tomsmeding> | % A.elems $ A.accumArray (+) 0 (0,3) (zip [0,0,0,2] [1,2,3,4]) |
| 2025-09-20 09:12:24 | <yahb2> | [6,0,4,0] |
| 2025-09-20 09:12:52 | <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 09:13:11 | <tomsmeding> | if the permutation is bijective, i.e. you have no overlap, no monoid is required, as you've seen |
| 2025-09-20 09:13:18 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 258 seconds) |
| 2025-09-20 09:13:33 | <tomsmeding> | (1+2+3 = 6) |
| 2025-09-20 09:14:05 | <tomsmeding> | @let import qualified Data.Array as A |
| 2025-09-20 09:14:06 | <lambdabot> | Defined. |
| 2025-09-20 09:14:15 | <tomsmeding> | > A.elems $ A.accumArray (+) 0 (0,3) (zip [0,0,0,2] [a,b,c,d]) |
| 2025-09-20 09:14:17 | <lambdabot> | [0 + a + b + c,0,0 + d,0] |
| 2025-09-20 09:14:20 | <tomsmeding> | nice |
All times are in UTC.