Logs: freenode/#haskell
| 2021-03-04 22:42:16 | <qih> | swarmcollective: Ey. |
| 2021-03-04 22:42:20 | → | theelous3 joins (~theelous3@unaffiliated/theelous3) |
| 2021-03-04 22:44:16 | → | heatsink joins (~heatsink@2600:1700:bef1:5e10:b42a:6451:2211:3708) |
| 2021-03-04 22:44:21 | → | conal joins (~conal@64.71.133.70) |
| 2021-03-04 22:46:18 | × | fendor_ quits (~fendor@91.141.0.22.wireless.dyn.drei.com) (Remote host closed the connection) |
| 2021-03-04 22:46:29 | <monochrom> | I don't understand why "map issueToDataRow issues []" is not the empty list. |
| 2021-03-04 22:46:40 | <monochrom> | Or if it is the empty list, what's the point of the rest. |
| 2021-03-04 22:47:57 | <Axman6> | what are there too many arguments |
| 2021-03-04 22:48:11 | <Axman6> | Hmm, that was a deeper question than I intended |
| 2021-03-04 22:48:36 | <swarmcollective> | Axman6: :D Good one. |
| 2021-03-04 22:49:37 | × | pera quits (~pera@unaffiliated/pera) (Quit: leaving) |
| 2021-03-04 22:49:54 | <monochrom> | I would agree with "deep trouble". |
| 2021-03-04 22:50:06 | <monochrom> | OK I misread. |
| 2021-03-04 22:51:12 | <monochrom> | dataRow (concat (catMaybes $ map issueToDataRow issues)) [] |
| 2021-03-04 22:51:15 | → | ByteEater joins (57cd846a@gateway/web/cgi-irc/kiwiirc.com/ip.87.205.132.106) |
| 2021-03-04 22:52:38 | → | wroathe joins (~wroathe@c-68-54-25-135.hsd1.mn.comcast.net) |
| 2021-03-04 22:53:18 | → | stree joins (~stree@68.36.8.116) |
| 2021-03-04 22:55:26 | <shachaf> | :t mapMaybe |
| 2021-03-04 22:55:27 | <lambdabot> | (a -> Maybe b) -> [a] -> [b] |
| 2021-03-04 22:55:39 | <ByteEater> | If qsort is the popular toy quicksort implementation in Haskell, does \l -> head $ drop (length l `div` 2) $ qsort l give the median of a non-empty list l in linear time for sure? Or does it depend on whether the implementation performs some optimization? Does GHC? |
| 2021-03-04 22:57:57 | <shachaf> | It certainly isn't for sure, since it might pick bad pivots. |
| 2021-03-04 22:58:18 | → | ech joins (~user@gateway/tor-sasl/ech) |
| 2021-03-04 22:58:24 | × | conal quits (~conal@64.71.133.70) (Quit: Computer has gone to sleep.) |
| 2021-03-04 22:58:28 | <ByteEater> | shachaf, I'm counting on laziness |
| 2021-03-04 22:58:34 | → | bahamas joins (~lucian@unaffiliated/bahamas) |
| 2021-03-04 22:58:49 | <shachaf> | What's the implementation of qsort here? |
| 2021-03-04 22:58:56 | → | __minoru__shirae joins (~shiraeesh@109.166.56.118) |
| 2021-03-04 22:59:17 | <ph88> | monochrom, your solution does not work .. it would be equivelant to do the following in the example https://hackage.haskell.org/package/hvega-0.11.0.0/docs/Graphics-Vega-VegaLite.html#v:dataFromRows [ ( "Animal", Str "Fish" ), ( "Age", Number 28 ), ( "Year", Str "2010" ), ( "Animal", Str "Dog" ), ( "Age", Number 12 ), ( "Year", Str "2014" ), ( "Animal", Str "Cat" ), ( "Age", Number 6 ), ( "Year", Str "2015" ) ]] |
| 2021-03-04 22:59:24 | <ByteEater> | if I had e.g. take 5 instead, it'd be linear, the rest would just remain unevaluated, no recursive calls into unneeded partitions would be performed |
| 2021-03-04 22:59:29 | <ph88> | that leaves me with only 1 row where values overwrite each other |
| 2021-03-04 22:59:31 | <monochrom> | base's Data.List.sort does not use quicksort at all. Some kind of mergesort-style but novel algorithm someone wrote and benchmarked to be good. |
| 2021-03-04 22:59:58 | → | Kaiepi joins (~Kaiepi@47.54.252.148) |
| 2021-03-04 23:00:19 | <dolio> | Laziness isn't going to save you from a worst case quicksort input. |
| 2021-03-04 23:00:48 | × | Tario quits (~Tario@201.192.165.173) (Ping timeout: 260 seconds) |
| 2021-03-04 23:01:29 | <shachaf> | To pick good pivots for sure, you need to be able to compute the median. |
| 2021-03-04 23:01:36 | <ByteEater> | shachaf, it's qsort l = if null l then [] else let (lo,hi) = partition (< head l) (tail l) in qsort lo ++ [head l] ++ qsort hi |
| 2021-03-04 23:01:39 | <Axman6> | ByteEater: the easiest way to confirm the answer is to step through the evaluation by hand. It definitely sounds like what you want is not possible though |
| 2021-03-04 23:02:19 | <Axman6> | if that list is already sorted you 're gonna have a bad time |
| 2021-03-04 23:02:23 | <ByteEater> | Axman6, so no fusion or rewrite rules would kick in and give me linear complexity? |
| 2021-03-04 23:02:29 | <Axman6> | no |
| 2021-03-04 23:02:37 | <Axman6> | I don't think linear median is even possible? |
| 2021-03-04 23:02:50 | <shachaf> | It is possible, but tricky. |
| 2021-03-04 23:02:57 | <ByteEater> | it is, all positional statistics are |
| 2021-03-04 23:03:24 | × | gehmehgeh quits (~ircuser1@gateway/tor-sasl/gehmehgeh) (Quit: Leaving) |
| 2021-03-04 23:04:06 | <Axman6> | so with Data.List's sort function, the bottom k elements can be found in O(n log k) IIRC, using take k . sort |
| 2021-03-04 23:04:11 | <monochrom> | Linear median is one of those things you never have the solution off the top of you head, you just always crack open CLRS again. :) |
| 2021-03-04 23:04:18 | × | bahamas quits (~lucian@unaffiliated/bahamas) (Ping timeout: 260 seconds) |
| 2021-03-04 23:04:19 | <ByteEater> | shachaf, Axman6, pleas hear me out, I don't want the whole sorted list back, just 1 element of it; e.g. this is a known feat of laziness that the following gives the 5 lowest items in linear time: take 5 . qsort |
| 2021-03-04 23:04:44 | <dolio> | Not for qsort it isn't. |
| 2021-03-04 23:04:48 | <Axman6> | no one actually uses quicksort in Haskell |
| 2021-03-04 23:05:08 | <Axman6> | because lazy merge sort is basically better in every way |
| 2021-03-04 23:05:28 | → | conal joins (~conal@64.71.133.70) |
| 2021-03-04 23:06:22 | <monochrom> | Laziness alone doesn't save you. You need to combine laziness with an algorithm that befriends that laziness. |
| 2021-03-04 23:06:24 | <ByteEater> | dolio, how so? I can visualize the call tree in my head with only 5 paths being fully evaluated, down to single elements, while most of the tree is hidden in unevaluated thunks |
| 2021-03-04 23:06:27 | <dolio> | Well, I guess it's techincally linear time, because 5*n is linear. |
| 2021-03-04 23:06:46 | <ByteEater> | yup, that's what I had in mind |
| 2021-03-04 23:06:48 | <dolio> | But if it's 'half way through the list', it's going to be n^2 worst case. |
| 2021-03-04 23:07:12 | <infinisil> | Axman6: Even for vectors/arrays? |
| 2021-03-04 23:07:44 | <ByteEater> | indeed, but can some fusion optimization or rewrite rule make the compiler see that I don't need the previous values, I'm dropping them? |
| 2021-03-04 23:07:53 | <Axman6> | O(1) access to elements changes things a lot |
| 2021-03-04 23:08:15 | <ByteEater> | well, O(log(n)), technically |
| 2021-03-04 23:08:44 | <infinisil> | Arrays/vectors are O(1) |
| 2021-03-04 23:08:53 | <infinisil> | Axman6: But yeah makes sense |
| 2021-03-04 23:08:56 | <monochrom> | All rewrite rules I've seen improve only constant multipliers. |
| 2021-03-04 23:08:59 | <infinisil> | Looking at https://hackage.haskell.org/package/vector-algorithms |
| 2021-03-04 23:09:26 | <Axman6> | yeah, vector-algorithms implementes lots of useful sorts, but they're not really relevant to the discussion of sorting lists |
| 2021-03-04 23:09:33 | × | danvet quits (~Daniel@2a02:168:57f4:0:efd0:b9e5:5ae6:c2fa) (Ping timeout: 272 seconds) |
| 2021-03-04 23:09:59 | <dolio> | Well, you can use them to sort lists by creating a temporary vector and sorting that, but it's going to sort the whole thing. |
| 2021-03-04 23:10:28 | <monochrom> | This would be one of those times you would hear me say again "you don't have enough hands-on experience to know what you're talking about regarding laziness or fusion or whatnot". |
| 2021-03-04 23:10:35 | <Axman6> | ByteEater: so in your quicksort implementation, don't forget that if youi pass it a sorted list, then the partition has to traverse the entire list before it can produce the [] for the lo side, and that happens in every recursive call |
| 2021-03-04 23:10:58 | <monochrom> | But last time I did that, people stoned me to death for "you're shutting them down". |
| 2021-03-04 23:11:03 | <ByteEater> | disregard what I wrote about vector, I forgot it only uses Int indices, not arbitrarily large |
| 2021-03-04 23:11:27 | <dolio> | Only enough to run a supercomputer out of memory. |
| 2021-03-04 23:11:29 | <monochrom> | So this time I won't shut it down, I'll just watch you people circle**** it to no end. |
| 2021-03-04 23:11:43 | <infinisil> | I guess since conversion to/from a vector is O(n), if you need to sort the whole list this might not be a terrible idea |
| 2021-03-04 23:11:56 | Axman6 | resists bringing up the discrimination package |
| 2021-03-04 23:12:13 | × | romesrf quits (~romesrf@44.190.189.46.rev.vodafone.pt) (Quit: WeeChat 3.0.1) |
| 2021-03-04 23:12:43 | <infinisil> | :o |
| 2021-03-04 23:13:28 | <Axman6> | Oops, too late |
| 2021-03-04 23:13:31 | × | heatsink quits (~heatsink@2600:1700:bef1:5e10:b42a:6451:2211:3708) (Remote host closed the connection) |
| 2021-03-04 23:13:36 | <infinisil> | Hm wait, what's the deal with discrimination? |
| 2021-03-04 23:13:39 | × | wroathe quits (~wroathe@c-68-54-25-135.hsd1.mn.comcast.net) (Ping timeout: 260 seconds) |
| 2021-03-04 23:13:40 | <Axman6> | Who needs linear time sorting anyway |
| 2021-03-04 23:13:41 | <infinisil> | Where's the catch? |
| 2021-03-04 23:13:49 | infinisil | should read more |
| 2021-03-04 23:13:57 | <dolio> | Bad constant factors? |
| 2021-03-04 23:14:06 | × | Pickchea quits (~private@unaffiliated/pickchea) (Quit: Leaving) |
| 2021-03-04 23:14:15 | → | madnificent_ joins (~madnifice@static.210.74.63.178.clients.your-server.de) |
| 2021-03-04 23:14:31 | <ByteEater> | "you don't have enough hands-on experience to know what you're talking about regarding laziness or fusion or whatnot" – well, somewhat true probably, that's why I'm asking and hoping to encounter people who know better ;D |
| 2021-03-04 23:14:33 | <infinisil> | Sorting is fundamentally O(n log n), which can't be O(n) with constant factors |
| 2021-03-04 23:14:37 | <Axman6> | yeah it's not as fast as I would like, but it's still useful for things. the Grouping stuff gets you a long way to writing MapReduce efficiently |
| 2021-03-04 23:14:58 | <dolio> | Comparison sorting is O(n log n). |
| 2021-03-04 23:15:05 | <Axman6> | infinisil: _comparison based sorting_ is O(n log n) |
| 2021-03-04 23:15:16 | <dolio> | There are many well known O(n) sorts. |
| 2021-03-04 23:15:18 | <infinisil> | Oh right |
| 2021-03-04 23:15:19 | → | gurmble joins (~Thunderbi@freenode/staff/grumble) |
| 2021-03-04 23:15:28 | <Axman6> | if you have some sort of radix, then you can ge O(n) - and it turns out sum types give you a radix |
| 2021-03-04 23:15:29 | × | madnificent quits (~madnifice@static.210.74.63.178.clients.your-server.de) (Quit: ZNC 1.8.2 - https://znc.in) |
| 2021-03-04 23:15:29 | × | grumble quits (~Thunderbi@freenode/staff/grumble) (Quit: K-Lined) |
| 2021-03-04 23:15:51 | gurmble | is now known as grumble |
All times are in UTC.