Logs: liberachat/#haskell
| 2026-03-07 13:39:25 | <[exa]> | also do add bangs to all your datatype definitions (Pair !Ptr !Ptr, etc) |
| 2026-03-07 13:39:48 | <[exa]> | (except the ones where you know that laziness is required) |
| 2026-03-07 13:40:04 | → | merijn joins (~merijn@host-cl.cgnat-g.v4.dfn.nl) |
| 2026-03-07 13:41:02 | <Guest89> | I mean the primary data structure is itself one big list, but I'm still not sure whether laziness or not is the way to go |
| 2026-03-07 13:42:41 | <[exa]> | well lmk if these 2 things change anything, if not I'd say we profile again and see |
| 2026-03-07 13:43:01 | <Guest89> | I've cut off about 30% of the allocations so far with it |
| 2026-03-07 13:43:03 | <Guest89> | do you want a new profile? |
| 2026-03-07 13:43:23 | <[exa]> | oh cool |
| 2026-03-07 13:43:42 | <Guest89> | we could move to a separate chat if you want |
| 2026-03-07 13:44:17 | <[exa]> | btw you can write that case-y comparison as: `compare s1 s2 <> compare r1 r2 <> compare ishigh1 ishigh2` |
| 2026-03-07 13:44:24 | <Guest89> | ooo |
| 2026-03-07 13:44:50 | × | merijn quits (~merijn@host-cl.cgnat-g.v4.dfn.nl) (Ping timeout: 248 seconds) |
| 2026-03-07 13:45:39 | <[exa]> | btw do you store these things in some kindof priority queue or ordered container or so? |
| 2026-03-07 13:45:51 | <Guest89> | yes |
| 2026-03-07 13:45:57 | <[exa]> | so a priority list? |
| 2026-03-07 13:46:02 | <Guest89> | it's not as much of a hot spot as I expected |
| 2026-03-07 13:46:20 | <[exa]> | just in case lemme find my quickhacked heapqueue implementation |
| 2026-03-07 13:46:27 | <Guest89> | right now it's just a red-black tree so it's not an optimal priority queue |
| 2026-03-07 13:46:42 | <Guest89> | I was conisdering using I think it's called PQueue? |
| 2026-03-07 13:46:51 | <Guest89> | the only asymptotic difference is constant or log time lookup though |
| 2026-03-07 13:47:43 | <Guest89> | otherwise I have some toy implementations from chris okasaki's book but it's, uhh, not working as intended right now |
| 2026-03-07 13:48:09 | <[exa]> | PQueues are great IF you need to also pick the elements by some index |
| 2026-03-07 13:48:21 | <[exa]> | if not they are strictly slower than a manual arrayheap |
| 2026-03-07 13:48:28 | <Guest89> | I only ever need the smallest element |
| 2026-03-07 13:48:41 | <Guest89> | part of my thesis involves *not* using arrays though |
| 2026-03-07 13:49:27 | <[exa]> | tuple is also an array |
| 2026-03-07 13:49:30 | [exa] | hides |
| 2026-03-07 13:49:47 | <haskellbridge> | <loonycyborg> if you ever need smallest element you can use set |
| 2026-03-07 13:50:01 | <[exa]> | +1 for set, not too slow at all |
| 2026-03-07 13:50:36 | <[exa]> | anyway I ended up replacing pqueue with this (the code is essentially a multi-stream merge): https://paste.tomsmeding.com/UskOMkBm, was like 3x faster |
| 2026-03-07 13:51:41 | <[exa]> | (apologies for the streaming mess around) |
| 2026-03-07 13:52:32 | <[exa]> | (missing def.: ofKey (a :> _) = a ) |
| 2026-03-07 13:55:52 | → | merijn joins (~merijn@host-cl.cgnat-g.v4.dfn.nl) |
| 2026-03-07 14:00:55 | × | merijn quits (~merijn@host-cl.cgnat-g.v4.dfn.nl) (Ping timeout: 264 seconds) |
| 2026-03-07 14:07:26 | <Guest89> | well the point is more that the data structures should be limited to trees and lists |
| 2026-03-07 14:08:00 | <Guest89> | exa do you have a reference description of the data structure? |
| 2026-03-07 14:11:39 | → | merijn joins (~merijn@host-cl.cgnat-g.v4.dfn.nl) |
| 2026-03-07 14:12:06 | <Guest89> | oh damn, strict data actually massively improved the runtime on larger inputs |
| 2026-03-07 14:16:50 | × | merijn quits (~merijn@host-cl.cgnat-g.v4.dfn.nl) (Ping timeout: 256 seconds) |
| 2026-03-07 14:25:17 | → | merijn joins (~merijn@host-cl.cgnat-g.v4.dfn.nl) |
| 2026-03-07 14:28:35 | → | simpleshun joins (~simpleshu@user/SimpleShun) |
| 2026-03-07 14:32:17 | × | merijn quits (~merijn@host-cl.cgnat-g.v4.dfn.nl) (Ping timeout: 252 seconds) |
| 2026-03-07 14:43:20 | → | merijn joins (~merijn@host-cl.cgnat-g.v4.dfn.nl) |
| 2026-03-07 14:47:53 | → | GdeVolpi1 joins (~GdeVolpia@user/GdeVolpiano) |
| 2026-03-07 14:48:19 | × | merijn quits (~merijn@host-cl.cgnat-g.v4.dfn.nl) (Ping timeout: 264 seconds) |
| 2026-03-07 14:48:25 | × | GdeVolpiano quits (~GdeVolpia@user/GdeVolpiano) (Read error: Connection reset by peer) |
| 2026-03-07 14:52:21 | → | AlexNoo_ joins (~AlexNoo@178.34.150.243) |
| 2026-03-07 14:52:42 | <[exa]> | Guest89: oh great :) |
| 2026-03-07 14:53:07 | → | AlexNoo__ joins (~AlexNoo@178.34.150.243) |
| 2026-03-07 14:53:12 | <[exa]> | Guest89: the structure is a completely normal binary heap in array, makeHeap and related stuff is on wiki |
| 2026-03-07 14:53:29 | <Guest89> | I think for the purposes of my thesis it's invalid because I theoretically can't rely on random access |
| 2026-03-07 14:54:33 | <[exa]> | wait why not (you're proving that something can be done purely?) |
| 2026-03-07 14:54:46 | <Guest89> | yes |
| 2026-03-07 14:54:52 | <[exa]> | I kinda thought that this is the implementation of the system where you're proving stuff |
| 2026-03-07 14:55:10 | <[exa]> | anyway if that's the case, Data.Set is pure and should be quite fast too. |
| 2026-03-07 14:55:22 | <Guest89> | Data.Set is probably a fine compromise for the moment |
| 2026-03-07 14:55:35 | × | AlexNoo quits (~AlexNoo@178.34.150.243) (Ping timeout: 245 seconds) |
| 2026-03-07 14:56:09 | <Guest89> | I may have to investigate more specialized data structures depending on whether or not I am brave enough to try to make the implementation work on the disk |
| 2026-03-07 14:56:42 | → | AlexNoo joins (~AlexNoo@178.34.150.243) |
| 2026-03-07 14:56:50 | × | AlexNoo_ quits (~AlexNoo@178.34.150.243) (Ping timeout: 248 seconds) |
| 2026-03-07 14:57:22 | × | AlexNoo__ quits (~AlexNoo@178.34.150.243) (Ping timeout: 248 seconds) |
| 2026-03-07 14:57:25 | → | AlexNoo_ joins (~AlexNoo@178.34.150.243) |
| 2026-03-07 14:58:09 | → | AlexNoo__ joins (~AlexNoo@178.34.150.243) |
| 2026-03-07 14:58:14 | <[exa]> | iirc there's some way to make a functionally-friendly heap but I don't recall any ATM... probably some version of the binomial one should behave nicely |
| 2026-03-07 14:58:59 | <Guest89> | Chris Okasaki's book has a few examples |
| 2026-03-07 14:59:04 | <Guest89> | including a binomial heap |
| 2026-03-07 14:59:17 | <[exa]> | well I should finally find time to read that one in full |
| 2026-03-07 14:59:36 | <Guest89> | ideally I need a purely functional and I/O-efficient at the same time but that has never been described in any literature |
| 2026-03-07 14:59:52 | <Guest89> | so either I need to take the (relatively small) performance loss or invent a whole new kind of wheel in the process |
| 2026-03-07 15:00:31 | <Guest89> | would be nice to have constant time lookup at least though |
| 2026-03-07 15:00:37 | <[exa]> | btw what's the whole thing about? |
| 2026-03-07 15:00:52 | <Guest89> | https://dl.acm.org/doi/10.1145/2429069.2429077 |
| 2026-03-07 15:00:55 | <[exa]> | (kinda curious, because it looks like you're proving something directly on the haskell code) |
| 2026-03-07 15:01:06 | × | AlexNoo quits (~AlexNoo@178.34.150.243) (Ping timeout: 248 seconds) |
| 2026-03-07 15:01:20 | <Guest89> | and https://ssoelvsten.github.io/adiar/ |
| 2026-03-07 15:01:38 | × | AlexNoo_ quits (~AlexNoo@178.34.150.243) (Ping timeout: 248 seconds) |
| 2026-03-07 15:01:39 | <Guest89> | I'm not a proof guy, I just wanted the best tools to support the limitations provided by the paper I linked |
| 2026-03-07 15:02:00 | <Guest89> | basically I'm trying make the first purely functional implementation of an I/O-efficient algorithm |
| 2026-03-07 15:02:38 | <Guest89> | and hopefully also demonstrate that the bounds are the same in either paradigm (i.e. compared to imperative) |
| 2026-03-07 15:02:42 | × | AlexNoo__ quits (~AlexNoo@178.34.150.243) (Ping timeout: 248 seconds) |
| 2026-03-07 15:03:02 | × | m_a_r_k quits (~m_a_r_k@archlinux/support/mark) (Read error: Connection reset by peer) |
| 2026-03-07 15:03:47 | × | Digit quits (~user@user/digit) (Ping timeout: 244 seconds) |
| 2026-03-07 15:04:09 | <Guest89> | but haskell is a good candidate for *specification* template because it's got a very presentable syntax and it has a decent compromise between being very close to total functional/proof assistant syntax while still having very mature libraries and performance |
| 2026-03-07 15:04:15 | <Guest89> | (and then there's laziness as we've discussed) |
| 2026-03-07 15:04:53 | <[exa]> | ahhhhhhhhhhh |
| 2026-03-07 15:05:00 | <[exa]> | okay now it makes sense |
| 2026-03-07 15:06:40 | <[exa]> | tbh I'd recommend splitting of a "clean" version and a "provably same but fast" version, like you suggested before |
| 2026-03-07 15:06:52 | <[exa]> | make yourself a newtype for list and call it "priority queue" |
| 2026-03-07 15:07:10 | <[exa]> | in the benchmarking version you change only this newtype and handling functions, and plug in anything that is fast |
| 2026-03-07 15:07:14 | <Guest89> | the best candidate for a performant implementation would be in koka if you know the language but it's not mature at all |
| 2026-03-07 15:07:23 | <Guest89> | hmm maybe |
| 2026-03-07 15:07:26 | <[exa]> | you can make a quickcheck for equivalence |
| 2026-03-07 15:07:32 | <[exa]> | which "proves" it ;) |
| 2026-03-07 15:07:53 | <Guest89> | that's also not a bad idea, I was going to use quickcheck down the line anyway |
| 2026-03-07 15:08:07 | <[exa]> | koka ain't bad, maybe ask the authors for opinion, maybe they'd have some bright ideas on what to do there |
| 2026-03-07 15:08:09 | <Guest89> | I just didn't want to commit to a "clean" version before I had settled things like the type definitions |
| 2026-03-07 15:08:37 | <Guest89> | I've actually spoken to one of the contributors before but they're not involved with the I/O algorithm part of it |
| 2026-03-07 15:09:00 | <Guest89> | but one restriction that I *theoretically* have is the need for deep copying, which koka seems to have built in |
| 2026-03-07 15:09:25 | <[exa]> | well, yeah. |
| 2026-03-07 15:09:43 | ← | L29Ah parts (~L29Ah@wikipedia/L29Ah) () |
All times are in UTC.