Logs: freenode/#haskell
| 2021-03-03 17:21:08 | <edwardk> | its not that bad really. you can define such a thing by looking at what showsPrec does |
| 2021-03-03 17:21:12 | <edwardk> | :t showsPrec |
| 2021-03-03 17:21:14 | <lambdabot> | Show a => Int -> a -> ShowS |
| 2021-03-03 17:21:36 | <edwardk> | so define newtype Expr = Expr { runExpr :: Int -> ShowS } -- |
| 2021-03-03 17:21:48 | <edwardk> | and the show instance is easy to write |
| 2021-03-03 17:22:10 | <edwardk> | and Num, etc. just build bigger expressions |
| 2021-03-03 17:22:45 | <edwardk> | iirc the actual implementation also carries around an optional number in case it can be computed and might support common sub-expression elimination if you use a specific way of accessing it, but the moral equivalent is easy |
| 2021-03-03 17:23:22 | <falsifian> | Cool. |
| 2021-03-03 17:24:19 | <falsifian> | Hm. Cabal's Distribution.Verbosity module has a notion of a "timestamp" flag that can be included in the verbosity settings, but I'm having trouble figuring out how to set that from the command-line, if it's possible at all |
| 2021-03-03 17:24:19 | × | emmanuel_erc quits (~user@2603-7000-9600-01c9-0000-0000-0000-0874.res6.spectrum.com) (Read error: Connection reset by peer) |
| 2021-03-03 17:24:32 | → | emmanuel_erc joins (~user@2603-7000-9600-01c9-0000-0000-0000-0874.res6.spectrum.com) |
| 2021-03-03 17:24:42 | × | boxscape quits (4ff0baf3@gateway/web/cgi-irc/kiwiirc.com/ip.79.240.186.243) (Quit: Connection closed) |
| 2021-03-03 17:25:17 | → | chenshen joins (~chenshen@2620:10d:c090:400::5:9f47) |
| 2021-03-03 17:26:30 | → | tzh joins (~tzh@c-24-21-73-154.hsd1.or.comcast.net) |
| 2021-03-03 17:26:32 | → | boxscape joins (4ff0baf3@gateway/web/cgi-irc/kiwiirc.com/ip.79.240.186.243) |
| 2021-03-03 17:26:47 | <falsifian> | Aha. cabal build --verbose='normal+timestamp' |
| 2021-03-03 17:28:31 | <falsifian> | So then I get lines like "1614792431.851 Building async-2.2.3 (lib)" and "1614792434.801 Completed async-2.2.3 (lib)"; from here I can just do some hacky post-processing. |
| 2021-03-03 17:29:13 | → | geowiesnot_bis joins (~user@87-89-181-157.abo.bbox.fr) |
| 2021-03-03 17:30:43 | → | nineonine joins (~nineonine@2604:3d08:7785:9600:2076:7626:28f5:58b2) |
| 2021-03-03 17:30:43 | × | emmanuel_erc quits (~user@2603-7000-9600-01c9-0000-0000-0000-0874.res6.spectrum.com) (Read error: Connection reset by peer) |
| 2021-03-03 17:31:08 | → | emmanuel_erc joins (~user@2603-7000-9600-01c9-0000-0000-0000-0874.res6.spectrum.com) |
| 2021-03-03 17:34:17 | × | geowiesnot_bis quits (~user@87-89-181-157.abo.bbox.fr) (Ping timeout: 265 seconds) |
| 2021-03-03 17:34:41 | × | Yumasi quits (~guillaume@2a01:e0a:5cb:4430:4f52:603c:a9c0:87e8) (Ping timeout: 258 seconds) |
| 2021-03-03 17:35:51 | × | geekosaur quits (82650c7a@130.101.12.122) (Quit: Connection closed) |
| 2021-03-03 17:36:33 | → | geekosaur joins (82650c7a@130.101.12.122) |
| 2021-03-03 17:37:07 | × | forgottenone quits (~forgotten@176.88.30.190) (Read error: Connection reset by peer) |
| 2021-03-03 17:37:19 | × | sm2n quits (~sm2n@bras-base-hmtnon143hw-grc-15-70-54-78-219.dsl.bell.ca) (Read error: Connection reset by peer) |
| 2021-03-03 17:37:21 | → | fendor joins (~fendor@91.141.0.81.wireless.dyn.drei.com) |
| 2021-03-03 17:39:34 | → | sm2n joins (~sm2n@bras-base-hmtnon143hw-grc-15-70-54-78-219.dsl.bell.ca) |
| 2021-03-03 17:39:39 | × | jrqc quits (~rofl@96.78.87.197) (Ping timeout: 245 seconds) |
| 2021-03-03 17:39:55 | <ADG1089__> | any fast algorithms for `\Sum_{x \in X, y \in Y, xy <= L} xy` ? |
| 2021-03-03 17:41:44 | <[exa]> | ADG1089__: how "fast" you want to get? you won't get better than O(n^2) in the general case |
| 2021-03-03 17:41:44 | × | ixlun quits (~user@213.205.241.12) (Read error: Connection reset by peer) |
| 2021-03-03 17:42:23 | <carbolymer> | what was the name of ghc option for inverse errors? |
| 2021-03-03 17:42:37 | <carbolymer> | my ddg-fu has failed me |
| 2021-03-03 17:42:50 | → | ixlun joins (~user@213.205.241.12) |
| 2021-03-03 17:43:09 | → | jrqc joins (~rofl@96.78.87.197) |
| 2021-03-03 17:43:21 | <carbolymer> | carbolymer: -freverse-errors |
| 2021-03-03 17:43:26 | <carbolymer> | carbolymer: thx |
| 2021-03-03 17:43:40 | <[exa]> | ADG1089__: if the limit L filters out a large portion of the numbers, sort both series and avoid matching `xz` for `z>y` if you already know `xy > L` |
| 2021-03-03 17:44:08 | <[exa]> | a.k.a. walk the hyperbola |
| 2021-03-03 17:44:15 | <ADG1089__> | [exa]: what if I have them already sorted? |
| 2021-03-03 17:44:20 | × | emmanuel_erc quits (~user@2603-7000-9600-01c9-0000-0000-0000-0874.res6.spectrum.com) (Read error: Connection reset by peer) |
| 2021-03-03 17:44:37 | <[exa]> | ADG1089__: then you suddenly have much less work |
| 2021-03-03 17:45:07 | <ADG1089__> | also this is for 2 lists, say I have n lists X1, X2, ... I am trying to find x1.x2... forall x1.x2.. <= L, where all Xi's are sorted |
| 2021-03-03 17:45:21 | <edwardk> | adg: yes. start with fingertrees just to have a stock data structure, put the values in X sorted into one the values in Y sorted into the other. use the sum as the monoid. Now. you can walk through the shorter of X or Y, then quickly cut the other at where the individual element x in X * the measure of the prefix of Y crosses L. |
| 2021-03-03 17:45:42 | <ADG1089__> | [exa]: I think using 2 pointers might work, which move in opposite direction one on each of the list |
| 2021-03-03 17:46:12 | <edwardk> | the cost should be ~ O(min(|X| log |Y|, |Y| log |X|)) |
| 2021-03-03 17:46:18 | → | Guest_88 joins (5619784f@cpc143846-cosh20-2-0-cust78.6-1.cable.virginm.net) |
| 2021-03-03 17:46:36 | <[exa]> | ADG1089__: also, if working on numbers, you can coalesce a lot of multiplication by carefully updating the sum of `x`es and multiplying them all by once by a given `y` |
| 2021-03-03 17:46:42 | <edwardk> | or did i misunderstand the problem |
| 2021-03-03 17:47:02 | <merijn> | edwardk: tbh, sounds like just two IntSet might work? :p |
| 2021-03-03 17:47:06 | <ADG1089__> | edwardk: I think it can be done in O(|X| + |Y|) |
| 2021-03-03 17:47:35 | <edwardk> | merijn: the fingertree gives the access to the sum of all of Y the relevant Ys in constant time. |
| 2021-03-03 17:47:47 | <edwardk> | the intmap doesn't unless you preprocess it to store prefix sums |
| 2021-03-03 17:47:53 | <[exa]> | ADG1089__: are you working with numbers or generally something distributive, right? |
| 2021-03-03 17:49:06 | <ADG1089__> | working on Z_{10^12}/2^32 |
| 2021-03-03 17:49:21 | <ADG1089__> | i.e. {x mod 2^32 | x <= 10^12 } |
| 2021-03-03 17:49:32 | <ADG1089__> | also x>0 |
| 2021-03-03 17:49:34 | <edwardk> | ADG1089__: trying to exploit the fact that you can slide the finger rather than moving from the left hand side from scratch each time? you can come up with something, not sure i can prove easily it gets you to linear |
| 2021-03-03 17:49:59 | × | heatsink quits (~heatsink@2600:1700:bef1:5e10:dd5f:6f4f:a50:215d) (Remote host closed the connection) |
| 2021-03-03 17:52:09 | <[exa]> | yeah, on pre-sorted sequences and const-time "finger move" and addition/multiplication this should be linear |
| 2021-03-03 17:52:37 | <edwardk> | oh yeah, you can definitely get it to be linear |
| 2021-03-03 17:54:26 | <edwardk> | finger move is log time in the distance you move the finger, but you only sweep it through once in each direction |
| 2021-03-03 17:55:56 | <edwardk> | now, this is subject to caveats that I assume X and Y are non-negative. when they can be negative you have to solve all 4 quadrants separately, and if they are vector spaces and xy is a dot product it is also messy |
| 2021-03-03 17:56:09 | <[exa]> | is there a general "fold" that processes 2 sequences and can choose which one to pick the next element from? the shape of this is roughly the same as e.g. merge in mergesort. |
| 2021-03-03 17:56:57 | × | coot quits (~coot@37.30.55.141.nat.umts.dynamic.t-mobile.pl) (Quit: coot) |
| 2021-03-03 17:57:25 | → | coot joins (~coot@37.30.55.141.nat.umts.dynamic.t-mobile.pl) |
| 2021-03-03 17:57:28 | × | merijn quits (~merijn@83-160-49-249.ip.xs4all.nl) (Ping timeout: 276 seconds) |
| 2021-03-03 17:57:29 | <ADG1089__> | ok I got it how to get it in linear time for 2 lists |
| 2021-03-03 17:58:00 | <monochrom> | I am lazy so I just merge and then fold that. |
| 2021-03-03 17:58:06 | × | gioyik quits (~gioyik@gateway/tor-sasl/gioyik) (Ping timeout: 268 seconds) |
| 2021-03-03 17:58:24 | <edwardk> | ADG1089__: great i can stop writing up the code then =) |
| 2021-03-03 17:58:29 | <ADG1089__> | thinking about N lists (say of size n each), I am thinking I can process 2 at a time which will take n/2*2n=n and repeat this so then it will be done in O(nlogn) i think |
| 2021-03-03 17:58:48 | <ADG1089__> | edwardk: we never know, I might get to learn something new from what you write =) |
| 2021-03-03 17:59:01 | <[exa]> | ADG1089__: the product is xyzwq.... from all lists ? |
| 2021-03-03 17:59:05 | → | merijn joins (~merijn@83-160-49-249.ip.xs4all.nl) |
| 2021-03-03 17:59:05 | <ADG1089__> | yeah |
| 2021-03-03 18:00:31 | <[exa]> | one problem with adding dimensions to a task is that the volume increases pretty quickly |
| 2021-03-03 18:01:05 | <[exa]> | if you process 2 at time you will have to guess what is the "rest of the L" for you |
| 2021-03-03 18:02:52 | × | ADG1089__ quits (~aditya@122.163.250.138) (Remote host closed the connection) |
| 2021-03-03 18:03:06 | × | kuribas quits (~user@ptr-25vy0ia12wjqyp3p35k.18120a2.ip6.access.telenet.be) (Remote host closed the connection) |
| 2021-03-03 18:03:55 | → | heatsink joins (~heatsink@2600:1700:bef1:5e10:dd5f:6f4f:a50:215d) |
| 2021-03-03 18:05:45 | <[exa]> | hm, in 3D the set of "border conditions" is in fact 2D, so kinda suspecting this won't be as easy without some brutal trick. |
| 2021-03-03 18:05:50 | <[exa]> | (also 3SUM problem) |
| 2021-03-03 18:06:11 | CrabMan | sent a long message: < https://matrix.org/_matrix/media/r0/download/matrix.org/klLgreaAKSLlbJHaGkcSWXjO/message.txt > |
| 2021-03-03 18:06:52 | <geekosaur> | CrabMan: because you imported only the type constructor and not the data constructor |
| 2021-03-03 18:07:05 | <geekosaur> | try import ... (Tokens(..)) |
| 2021-03-03 18:07:15 | <geekosaur> | or (Tokens(Tokens)) |
| 2021-03-03 18:07:17 | × | newbie76 quits (4cbf11e9@node-17-233.flex.volo.net) (Quit: Connection closed) |
| 2021-03-03 18:08:14 | → | egp__ joins (~egp_@2.95.74.168) |
| 2021-03-03 18:08:42 | → | cole-h joins (~cole-h@c-73-48-197-220.hsd1.ca.comcast.net) |
| 2021-03-03 18:08:51 | × | egp_ quits (~egp_@2.95.74.168) (Quit: EXIT) |
| 2021-03-03 18:09:30 | <CrabMan> | import Text.Megaparsec (ErrorItem(Tokens)) |
| 2021-03-03 18:09:30 | <CrabMan> | it works, thanks |
| 2021-03-03 18:13:30 | → | gioyik joins (~gioyik@gateway/tor-sasl/gioyik) |
| 2021-03-03 18:15:29 | × | stree quits (~stree@68.36.8.116) (Ping timeout: 245 seconds) |
| 2021-03-03 18:15:34 | <dminuoso> | 17:05:18 merijn | aggin: Go's compiler was from the start engineered to be resource low |
| 2021-03-03 18:15:35 | × | deviantfero quits (~deviantfe@190.150.27.58) (Ping timeout: 240 seconds) |
| 2021-03-03 18:15:54 | <dminuoso> | It is considerably easy to implement a low-resource compiler for a low-feature language. |
All times are in UTC.