Newest at the top
| 2025-12-02 17:59:18 +0100 | <merijn> | c_wraith: I mean, for something like Int they are (given the completely broken big O model) |
| 2025-12-02 17:59:09 +0100 | <c_wraith> | I don't know why schools teach both of those data structures so poorly. |
| 2025-12-02 17:58:40 +0100 | tromp | (~textual@2001:1c00:3487:1b00:4073:6a24:b181:8b56) (Ping timeout: 245 seconds) |
| 2025-12-02 17:58:24 +0100 | <c_wraith> | but by way of fairness, a binary tree is only O(log n) for stuff if comparisons are O(1), which is equally impossible |
| 2025-12-02 17:58:19 +0100 | <merijn> | but that idea has been floating around since 2007 and still hasn't happened, so I would rather not hold my breath |
| 2025-12-02 17:58:00 +0100 | <merijn> | Now that could theoretically be fixed by decoupling base from GHC |
| 2025-12-02 17:57:45 +0100 | <merijn> | looncyborg: Counter point: Since base changes requires new GHC releases they're slow to become widely available |
| 2025-12-02 17:57:06 +0100 | <haskellbridge> | <loonycyborg> On the other hand it's just matter of putting it to .cabal file and many other packages already use them so they're pretty much guaranteed to be pulled in.. |
| 2025-12-02 17:56:00 +0100 | <c_wraith> | If you want to hash n values into O(n) buckets, you need to look at O(log n) bits of each value |
| 2025-12-02 17:55:16 +0100 | <c_wraith> | But it doesn't really matter that it's not O(1), because hashing isn't O(1) anyway, and never has been |
| 2025-12-02 17:54:51 +0100 | <c_wraith> | like, unordered-containers uses a HAMT instead of an array, because mutation forces you into an unpleasant API. That's a very fast data structure, but it's sure not O(1) for anything |
| 2025-12-02 17:54:11 +0100 | chromoblob | (~chromoblo@user/chromob1ot1c) chromoblob\0 |
| 2025-12-02 17:52:56 +0100 | <haskellbridge> | <loonycyborg> so people wouldn't have issues like above |
| 2025-12-02 17:52:40 +0100 | <haskellbridge> | <loonycyborg> I think both unordered and ordered containers should be part of base |
| 2025-12-02 17:52:26 +0100 | <c_wraith> | both constant time for hash tables and logarithmic time for binary trees are lies, of course |
| 2025-12-02 17:51:52 +0100 | <haskellbridge> | <loonycyborg> Constant time is still faster than logarithmic :P |
| 2025-12-02 17:51:49 +0100 | <c_wraith> | I rarely use unordered containers, for reasons of wanting to minimize dependencies and that collection performance usually doesn't matter. But whenever I've benchmarked my own code, it usually is faster. I just don't think it's enough faster to be worthwhile. |
| 2025-12-02 17:49:16 +0100 | Anarchos | (~Anarchos@91-161-254-16.subs.proxad.net) () |
| 2025-12-02 17:49:01 +0100 | <merijn> | Which pretty much brings us back to the initial question of "what's your key type and what makes you expect it's worth it to include Hashable over Ord" |
| 2025-12-02 17:43:48 +0100 | <merijn> | Not to mention the question whether that's even the hot part of your code |
| 2025-12-02 17:42:45 +0100 | <merijn> | c_wraith: I mean, that's entirely dependent on workload, key type, and access pattern |
| 2025-12-02 17:41:50 +0100 | <c_wraith> | (the higher branching factor of a HAMT over a binary tree is significant) |
| 2025-12-02 17:40:53 +0100 | <c_wraith> | I mean, unordered-containers is generally faster than containers. |
| 2025-12-02 17:38:17 +0100 | trickard_ | (~trickard@cpe-85-98-47-163.wireline.com.au) |
| 2025-12-02 17:36:27 +0100 | <merijn> | c_wraith: I'm not convinced that buys you anything over just straight up Map |
| 2025-12-02 17:35:03 +0100 | trickard | (~trickard@cpe-85-98-47-163.wireline.com.au) (Read error: Connection reset by peer) |
| 2025-12-02 17:34:51 +0100 | lucabtz | (~lucabtz@user/lucabtz) (Remote host closed the connection) |
| 2025-12-02 17:34:41 +0100 | <lucabtz> | yeah |
| 2025-12-02 17:34:32 +0100 | <c_wraith> | yeah, its a way of handling collisions that guarantees you'll never have an O(n) breakdown |
| 2025-12-02 17:33:56 +0100 | pr1sm | (~pr1sm@24.91.163.31) (Remote host closed the connection) |
| 2025-12-02 17:33:53 +0100 | <lucabtz> | i suppose it makes it constant time with no collisions and log n with collisions |
| 2025-12-02 17:33:48 +0100 | <merijn> | Regular Map already has O(log N) worst case, so the only reason not to use that if you expect K to have some expensive comparison |
| 2025-12-02 17:33:04 +0100 | <merijn> | lucabtz: Yes, but what type do you expect that makes it worth to include Hashable over just `Ord k`? |
| 2025-12-02 17:32:13 +0100 | <lucabtz> | k is the key i suppose |
| 2025-12-02 17:30:45 +0100 | <merijn> | What's k there? (i.e. is the Hashable even worth it?) |
| 2025-12-02 17:30:24 +0100 | <merijn> | Is that a thing? |
| 2025-12-02 17:28:13 +0100 | trickard_ | trickard |
| 2025-12-02 17:27:45 +0100 | trickard_ | (~trickard@cpe-85-98-47-163.wireline.com.au) |
| 2025-12-02 17:26:38 +0100 | pr1sm | (~pr1sm@24.91.163.31) |
| 2025-12-02 17:26:11 +0100 | <haskellbridge> | <Zemyla> Is there a module for semi-ordered hashmaps, ones that require (Ord k, Hashable k), and as such have O(log n) worst-case performance? |
| 2025-12-02 17:25:45 +0100 | pr1sm | (~pr1sm@2600:1000:b115:c9f2:64b7:10e9:a90c:5331) (Ping timeout: 245 seconds) |
| 2025-12-02 17:25:04 +0100 | trickard_ | (~trickard@cpe-85-98-47-163.wireline.com.au) (Read error: Connection reset by peer) |
| 2025-12-02 17:20:24 +0100 | pr1sm | (~pr1sm@2600:1000:b115:c9f2:64b7:10e9:a90c:5331) |
| 2025-12-02 17:20:01 +0100 | chromoblob | (~chromoblo@user/chromob1ot1c) (Ping timeout: 255 seconds) |
| 2025-12-02 17:15:51 +0100 | chromoblob | (~chromoblo@user/chromob1ot1c) chromoblob\0 |
| 2025-12-02 17:15:24 +0100 | chromoblob | (~chromoblo@user/chromob1ot1c) (Ping timeout: 244 seconds) |
| 2025-12-02 17:14:38 +0100 | trickard_ | (~trickard@cpe-85-98-47-163.wireline.com.au) |
| 2025-12-02 17:14:06 +0100 | Enrico63 | (~Enrico63@host-212-171-79-170.pool212171.interbusiness.it) (Quit: Client closed) |
| 2025-12-02 17:11:52 +0100 | trickard | (~trickard@cpe-85-98-47-163.wireline.com.au) (Read error: Connection reset by peer) |
| 2025-12-02 17:09:29 +0100 | Square | (~Square@user/square) (Ping timeout: 250 seconds) |