Newest at the top
| 2026-01-27 11:45:20 +0100 | trickard_ | (~trickard@cpe-80-98-47-163.wireline.com.au) |
| 2026-01-27 11:44:32 +0100 | vanishingideal | (~vanishing@user/vanishingideal) (Ping timeout: 240 seconds) |
| 2026-01-27 11:44:23 +0100 | Square | (~Square4@user/square) Square |
| 2026-01-27 11:42:56 +0100 | trickard_ | (~trickard@cpe-80-98-47-163.wireline.com.au) (Ping timeout: 265 seconds) |
| 2026-01-27 11:29:43 +0100 | vanishingideal | (~vanishing@user/vanishingideal) vanishingideal |
| 2026-01-27 11:28:53 +0100 | internatetional | (~nate@2404:c0:2447:3b47:188e:3e81:8514:389a) (Client Quit) |
| 2026-01-27 11:28:51 +0100 | internatetional | (~nate@2404:c0:2447:3b47:188e:3e81:8514:389a) internatetional |
| 2026-01-27 11:27:00 +0100 | fp | (~Thunderbi@2001-14ba-6e24-3000--198.rev.dnainternet.fi) (Ping timeout: 256 seconds) |
| 2026-01-27 11:25:32 +0100 | jreicher | (~joelr@user/jreicher) (Quit: Power outage) |
| 2026-01-27 11:23:28 +0100 | trickard_ | (~trickard@cpe-80-98-47-163.wireline.com.au) |
| 2026-01-27 11:19:15 +0100 | xff0x | (~xff0x@fsb6a9491c.tkyc517.ap.nuro.jp) (Ping timeout: 265 seconds) |
| 2026-01-27 11:16:40 +0100 | trickard_ | (~trickard@cpe-80-98-47-163.wireline.com.au) (Read error: Connection reset by peer) |
| 2026-01-27 11:13:43 +0100 | oskarw | (~user@user/oskarw) (Ping timeout: 246 seconds) |
| 2026-01-27 11:12:44 +0100 | trickard_ | (~trickard@cpe-80-98-47-163.wireline.com.au) |
| 2026-01-27 11:12:29 +0100 | trickard | (~trickard@cpe-80-98-47-163.wireline.com.au) (Ping timeout: 244 seconds) |
| 2026-01-27 11:12:27 +0100 | <gentauro> | tl;dw -> https://www.youtube.com/watch?v=8hJtTIkDr5U&t=241s (around 04:01 ish) |
| 2026-01-27 11:11:23 +0100 | jreicher | (~joelr@user/jreicher) jreicher |
| 2026-01-27 11:09:53 +0100 | jreicher | (~joelr@user/jreicher) (Quit: brb) |
| 2026-01-27 11:06:41 +0100 | <int-e> | (unless you want to distinguish between linear and quadratic growth, say, but I didn't do that) |
| 2026-01-27 11:06:06 +0100 | __monty__ | (~toonn@user/toonn) toonn |
| 2026-01-27 11:05:48 +0100 | <int-e> | jreicher: Anyway. The reason why I wrote up that example was to show that it wouldn't rely on any big patterns or huge numbers of arguments but stay polynomially bounded in the number of cases, at which point the precise parameter you pick stops to matter. |
| 2026-01-27 10:54:17 +0100 | <gentauro> | I really miss the hole eXchange concept :'( |
| 2026-01-27 10:53:56 +0100 | <gentauro> | I was actually there :) |
| 2026-01-27 10:53:29 +0100 | <gentauro> | int-e: and jreicher: I think I found the talk "Simon Peyton Jones - Pattern Match Warnings - How Hard Can It Be?" https://www.youtube.com/watch?v=8hJtTIkDr5U |
| 2026-01-27 10:52:01 +0100 | <int-e> | jreicher: you're still cross-attributing messages from me and gentauro |
| 2026-01-27 10:50:54 +0100 | <jreicher> | I'm just not seeing the problem definition clearly. I freely admit that. |
| 2026-01-27 10:50:45 +0100 | CiaoSen | (~Jura@2a02:8071:64e1:da0:5a47:caff:fe78:33db) (Ping timeout: 245 seconds) |
| 2026-01-27 10:50:18 +0100 | <int-e> | and also, in case that wasn't clear, you /can/ translate pattern matching without any blowup if you accept redundant matches |
| 2026-01-27 10:50:18 +0100 | <jreicher> | int-e: I know, which is why I was asking for a more specific definition before, but gentauro just offered "n" as the number of cases. |
| 2026-01-27 10:49:21 +0100 | <int-e> | so it's not analogous to strings at all |
| 2026-01-27 10:49:00 +0100 | <int-e> | jreicher: pattern matching isn't strictly left to right because of wildcard patterns |
| 2026-01-27 10:47:42 +0100 | <jreicher> | Hmm. I thought that would be nlogn. I haven't read the papers yet, but you have max n comparisons of logn length bitstrings |
| 2026-01-27 10:47:33 +0100 | <lambdabot> | [["olleh","lens","world"],["hello","snel","world"],["hello","lens","dlrow"]] |
| 2026-01-27 10:47:32 +0100 | <Axman6> | > map (\x -> peek (reverse (pos x)) x) $ holesOf traverse $ words "hello lens world" |
| 2026-01-27 10:47:10 +0100 | <int-e> | gentauro: an upper bound is not a hardness proof though :P |
| 2026-01-27 10:46:17 +0100 | <gentauro> | rather said, exhaustive PM. |
| 2026-01-27 10:46:05 +0100 | <gentauro> | so PM is a "very difficult" problem to solve |
| 2026-01-27 10:45:54 +0100 | <gentauro> | that's what I recall from the SPJ talk |
| 2026-01-27 10:45:32 +0100 | <gentauro> | jreicher: and int-e if you pm on `case (x_1, x_2, …, x_n) of …` then you will have an upperbound of 2^n cases |
| 2026-01-27 10:43:32 +0100 | oskarw | (~user@user/oskarw) oskarw |
| 2026-01-27 10:42:22 +0100 | marinelli | (~weechat@gateway/tor-sasl/marinelli) (Quit: marinelli) |
| 2026-01-27 10:39:38 +0100 | <tomsmeding> | which is, iirc, polynomially bounded by the collective size of the types it outputs (for all subterms), and thus only exponential if you give it a program that has exponentially large inferred types |
| 2026-01-27 10:38:50 +0100 | <tomsmeding> | ok so the GMTM paper undersells the problem a little bit, because it likens it to the complexity of hindley-milner |
| 2026-01-27 10:38:31 +0100 | <tomsmeding> | ah right |
| 2026-01-27 10:38:17 +0100 | <int-e> | And you can encode 3-SAT if you're checking pattern completeness. |
| 2026-01-27 10:37:58 +0100 | <tomsmeding> | sure, but you can typically turn a computation problem into a decision problem by checking whether the output satisfies some condition |
| 2026-01-27 10:37:28 +0100 | housemate | (~housemate@202.7.248.67) housemate |
| 2026-01-27 10:37:26 +0100 | <jreicher> | tomsmeding: IIRC output size isn't relevant to NP-completeness. That class is only defined for decision problems |
| 2026-01-27 10:36:23 +0100 | <int-e> | ...cases to keep track of. |
| 2026-01-27 10:36:17 +0100 | <int-e> | Where Haskell demands that you match the first argument, then optionally the fourth, then the second, then optionally the fifth, then the third argument, then optionally the sixth... and now if you want to avoid redundant pattern matches, you have to keep track of which of the first 3 arguments were equal to A when tackling the next 3 cases. And you can scale that up to 2*n arguments and 2^n... |