Logs: freenode/#haskell
| 2021-04-17 11:46:18 | → | nineonine joins (~nineonine@2604:3d08:7785:9600:68a6:8c79:2caf:5ce4) |
| 2021-04-17 11:48:08 | → | justanotheruser joins (~justanoth@unaffiliated/justanotheruser) |
| 2021-04-17 11:48:09 | → | LKoen joins (~LKoen@65.250.88.92.rev.sfr.net) |
| 2021-04-17 11:49:41 | → | ddellaco_ joins (~ddellacos@ool-44c73afa.dyn.optonline.net) |
| 2021-04-17 11:50:48 | × | fiedlr quits (~fiedlr@83.148.33.254) (Remote host closed the connection) |
| 2021-04-17 11:51:27 | → | fiedlr joins (~fiedlr@83.148.33.254) |
| 2021-04-17 11:54:08 | × | fiedlr quits (~fiedlr@83.148.33.254) (Read error: Connection reset by peer) |
| 2021-04-17 11:54:21 | × | ddellaco_ quits (~ddellacos@ool-44c73afa.dyn.optonline.net) (Ping timeout: 260 seconds) |
| 2021-04-17 11:54:44 | → | fiedlr joins (~fiedlr@83.148.33.254) |
| 2021-04-17 11:56:18 | → | ddellacosta joins (ddellacost@gateway/vpn/mullvad/ddellacosta) |
| 2021-04-17 11:57:34 | → | coot joins (~coot@37.30.50.130.nat.umts.dynamic.t-mobile.pl) |
| 2021-04-17 11:58:34 | → | heatsink joins (~heatsink@108-201-191-115.lightspeed.sntcca.sbcglobal.net) |
| 2021-04-17 12:00:02 | → | liyang joins (~liyang@90.255.129.199) |
| 2021-04-17 12:00:40 | × | ddellacosta quits (ddellacost@gateway/vpn/mullvad/ddellacosta) (Ping timeout: 252 seconds) |
| 2021-04-17 12:00:47 | × | fiedlr quits (~fiedlr@83.148.33.254) (Remote host closed the connection) |
| 2021-04-17 12:01:24 | → | fiedlr joins (~fiedlr@83.148.33.254) |
| 2021-04-17 12:02:56 | × | heatsink quits (~heatsink@108-201-191-115.lightspeed.sntcca.sbcglobal.net) (Ping timeout: 246 seconds) |
| 2021-04-17 12:05:10 | → | ADG1089 joins (~aditya@223.226.228.157) |
| 2021-04-17 12:05:33 | × | ADG1089 quits (~aditya@223.226.228.157) (Client Quit) |
| 2021-04-17 12:05:55 | × | fiedlr quits (~fiedlr@83.148.33.254) (Ping timeout: 265 seconds) |
| 2021-04-17 12:08:45 | → | heatsink joins (~heatsink@108-201-191-115.lightspeed.sntcca.sbcglobal.net) |
| 2021-04-17 12:10:36 | × | nineonine quits (~nineonine@2604:3d08:7785:9600:68a6:8c79:2caf:5ce4) (Ping timeout: 258 seconds) |
| 2021-04-17 12:13:10 | × | elfets quits (~elfets@ip-37-201-23-96.hsi13.unitymediagroup.de) (Ping timeout: 252 seconds) |
| 2021-04-17 12:13:11 | × | heatsink quits (~heatsink@108-201-191-115.lightspeed.sntcca.sbcglobal.net) (Ping timeout: 240 seconds) |
| 2021-04-17 12:18:45 | × | bitdex quits (~bitdex@gateway/tor-sasl/bitdex) (Ping timeout: 240 seconds) |
| 2021-04-17 12:19:09 | → | raehik joins (~raehik@cpc95906-rdng25-2-0-cust156.15-3.cable.virginm.net) |
| 2021-04-17 12:19:57 | → | ADG1089 joins (~aditya@223.226.228.157) |
| 2021-04-17 12:21:35 | → | bitdex joins (~bitdex@gateway/tor-sasl/bitdex) |
| 2021-04-17 12:22:32 | → | freegraph joins (~freegraph@103.58.155.187) |
| 2021-04-17 12:23:56 | <freegraph> | Just started learning haskell from learn you a haskell. It mentions that appending a list to list is slow, but why is that a case? Can't haskell simply store the pointer to the end of list, and use that to append another list? |
| 2021-04-17 12:27:09 | <exarkun> | freegraph: How is a Haskell list represented? |
| 2021-04-17 12:27:33 | <freegraph> | Per my understanding, it must be a linked list |
| 2021-04-17 12:27:48 | <freegraph> | https://www.haskelltutorials.com/guides/haskell-lists-ultimate-guide.html also says so |
| 2021-04-17 12:28:16 | → | dmytrish joins (~mitra@2a02:8084:a82:d900:319a:d200:a43d:3e3c) |
| 2021-04-17 12:28:20 | → | wroathe joins (~wroathe@c-68-54-25-135.hsd1.mn.comcast.net) |
| 2021-04-17 12:28:33 | <exarkun> | freegraph: Notably, a forward singly-linked list |
| 2021-04-17 12:28:50 | <exarkun> | freegraph: How do you know when you're at the end? |
| 2021-04-17 12:29:46 | <freegraph> | Can't it maintain a tail pointer? Everytime a new node is added, make next of tail to the new one, and then update tail to the new one |
| 2021-04-17 12:30:10 | <exarkun> | freegraph: What would that "update" look like? |
| 2021-04-17 12:30:39 | → | ddellacosta joins (ddellacost@gateway/vpn/mullvad/ddellacosta) |
| 2021-04-17 12:30:50 | <exarkun> | freegraph: Would it be an in-place modification to an existing value? |
| 2021-04-17 12:30:56 | → | nicholasbulka joins (~nicholasb@2601:900:4301:da0:c8b6:8ee4:f90a:54d2) |
| 2021-04-17 12:31:10 | → | geekosaur joins (930099da@rrcs-147-0-153-218.central.biz.rr.com) |
| 2021-04-17 12:31:37 | <freegraph> | A psuedocode would be like this. tail.next = newnode. tail = newnode |
| 2021-04-17 12:31:46 | → | lambdaman joins (~lambdaman@s66-183-152-156.bc.hsia.telus.net) |
| 2021-04-17 12:31:59 | <exarkun> | freegraph: How do you change a value in-place in Haskell? |
| 2021-04-17 12:32:05 | <freegraph> | Got it! Thanks! |
| 2021-04-17 12:32:33 | × | wroathe quits (~wroathe@c-68-54-25-135.hsd1.mn.comcast.net) (Ping timeout: 240 seconds) |
| 2021-04-17 12:32:39 | <freegraph> | It will take time to get used to this! |
| 2021-04-17 12:32:58 | → | fiedlr joins (~fiedlr@83.148.33.254) |
| 2021-04-17 12:33:58 | <exarkun> | :) |
| 2021-04-17 12:34:25 | → | berberman_ joins (~berberman@unaffiliated/berberman) |
| 2021-04-17 12:34:26 | <gehmehgeh> | exarkun: To be fair, there are things like Data.IORef ;) |
| 2021-04-17 12:34:59 | × | berberman quits (~berberman@unaffiliated/berberman) (Ping timeout: 248 seconds) |
| 2021-04-17 12:35:10 | × | ddellacosta quits (ddellacost@gateway/vpn/mullvad/ddellacosta) (Ping timeout: 252 seconds) |
| 2021-04-17 12:35:24 | <exarkun> | gehmehgeh: To be sure |
| 2021-04-17 12:36:14 | <gehmehgeh> | One can -- with a bit of handwaving -- basically change values "in-place" (for example, how else do you get user input etc). But that's not how things like the list type work |
| 2021-04-17 12:36:14 | × | lambdaman quits (~lambdaman@s66-183-152-156.bc.hsia.telus.net) (Ping timeout: 252 seconds) |
| 2021-04-17 12:37:02 | → | machinedgod joins (~machinedg@24.105.81.50) |
| 2021-04-17 12:37:17 | × | rprije quits (~rprije@59-102-63-15.tpgi.com.au) (Ping timeout: 260 seconds) |
| 2021-04-17 12:37:44 | → | ClaudiusMaximus joins (~claude@cpc98210-croy26-2-0-cust137.19-2.cable.virginm.net) |
| 2021-04-17 12:37:55 | × | ClaudiusMaximus quits (~claude@cpc98210-croy26-2-0-cust137.19-2.cable.virginm.net) (Changing host) |
| 2021-04-17 12:37:55 | → | ClaudiusMaximus joins (~claude@unaffiliated/claudiusmaximus) |
| 2021-04-17 12:38:45 | → | ericsagnes joins (~ericsagne@2405:6580:0:5100:4ca8:cdd0:c987:a338) |
| 2021-04-17 12:39:53 | × | ericsagn1 quits (~ericsagne@2405:6580:0:5100:f42f:2cd9:4893:4d87) (Ping timeout: 250 seconds) |
| 2021-04-17 12:41:28 | → | heatsink joins (~heatsink@108-201-191-115.lightspeed.sntcca.sbcglobal.net) |
| 2021-04-17 12:45:46 | × | heatsink quits (~heatsink@108-201-191-115.lightspeed.sntcca.sbcglobal.net) (Ping timeout: 252 seconds) |
| 2021-04-17 12:45:54 | <ski> | appending to list is not slow, in the sense that it just takes the expected amount of time, for a single-linked list. there's no way around chasing that chain of tails (except by switching to a different data structure). however, *repeatedly* appending to a list can be argued to be slower than one would initially expect, in the sense that if each append is done individually, you'll repeatedly be traversing |
| 2021-04-17 12:46:00 | <ski> | that list spine to the end, as opposed to batching it, only traversing once, adding all the stuff to the end in one go |
| 2021-04-17 12:47:52 | × | minoru_shiraeesh quits (~shiraeesh@5.101.59.131) (Ping timeout: 240 seconds) |
| 2021-04-17 12:48:23 | ski | . o O ( "Schlemiel the painter's algorithm" -- "Back to Basics" by Joel Spolsky in 2001-12-11 at <https://www.joelonsoftware.com/2001/12/11/back-to-basics/> ) |
| 2021-04-17 12:49:24 | → | minoru_shiraeesh joins (~shiraeesh@5.101.59.131) |
| 2021-04-17 12:49:47 | <liyang> | freegraph: fast appends is not what the singly-forward linked-list type is suited for. If that's an issue you'd really want a different data structure. Just try to understand how they work from a pedagogical point-of-view for now. |
| 2021-04-17 12:50:20 | → | jamm_ joins (~jamm@unaffiliated/jamm) |
| 2021-04-17 12:52:34 | <ski> | (to avoid this problem of repeatedly adding to the end getting you quadratic instead of the expected linear complexity, one can workaround this by instead adding to the front (prepending), and then, at the end of a processing, do a final reverse (in case the order is important). or, one can sometimes rephrase the processing to naturally add (shorter pieces) to the front instead. sometimes it may be nicer |
| 2021-04-17 12:52:40 | <ski> | with an accumulator. sometimes it's instead nicer writing it in direct style. one can also consider switching to "different lists", or to another data structure (like `Seq')) |
| 2021-04-17 12:53:20 | × | ADG1089 quits (~aditya@223.226.228.157) (Quit: Konversation terminated!) |
| 2021-04-17 12:53:28 | <ski> | (er, "difference lists", rather) |
| 2021-04-17 12:54:02 | <gehmehgeh> | often called "dlists" |
| 2021-04-17 12:54:16 | <gehmehgeh> | There's also a ready-made DList type, if I remember correctly |
| 2021-04-17 12:54:38 | <gehmehgeh> | exarkun: but that's for later, really. |
| 2021-04-17 12:55:24 | <freegraph> | ski, So appending two lists in quadratic? I thought it just appends the head of second list to tail of previous one. |
| 2021-04-17 12:55:29 | × | nicholasbulka quits (~nicholasb@2601:900:4301:da0:c8b6:8ee4:f90a:54d2) (Ping timeout: 250 seconds) |
| 2021-04-17 12:56:07 | <ski> | first you should understand the difference in association of list append, and how that causes a difference in complexity. and how that's related to accumulator vs. direct style |
| 2021-04-17 12:56:15 | <ski> | freegraph : no, that's not what i said |
| 2021-04-17 12:56:27 | <exarkun> | gehmehgeh: I didn't bring it up :) |
| 2021-04-17 12:56:35 | × | LKoen quits (~LKoen@65.250.88.92.rev.sfr.net) (Remote host closed the connection) |
| 2021-04-17 12:56:48 | <gehmehgeh> | exarkun: sorry, I meant freegraph |
| 2021-04-17 12:56:58 | <ski> | freegraph : `as ++ bs' is linear in the length of `as' (the length of `bs' doesn't matter) |
| 2021-04-17 12:57:54 | <freegraph> | ski, ok. Got it. So if we take all values of bs separately, then it would be quadratic in length of bs. |
| 2021-04-17 12:58:14 | <ski> | freegraph : however, consider `as ++ (bs ++ (cs ++ ds))'. this will traverse `as', and traverse `bs', and `cs', in order to perform the three appending operations. so if the lengths of `as',`bs',`cs',`ds' are `k',`l',`m',`n', then the expected time for this is `k + l + m' |
| 2021-04-17 12:58:28 | <freegraph> | Yes |
| 2021-04-17 12:59:33 | <ski> | freegraph : however, compare this with `((as ++ bs) ++ cs) ++ ds'. this will first traverse `as'. next it'll traverse (the copy of) `as', in addition to also traversing `bs'. next it'll again traverse (copies of) `as',`bs', and also `cs'. so the steps here are `k + (k + l) + (k + l + m)' |
| 2021-04-17 12:59:42 | → | urodna joins (~urodna@unaffiliated/urodna) |
| 2021-04-17 12:59:46 | × | minoru_shiraeesh quits (~shiraeesh@5.101.59.131) (Ping timeout: 240 seconds) |
| 2021-04-17 13:00:31 | <ski> | so, the right-associated nesting of `++' wins over the left-associated nesting (which is unexpectedly quadratic, in the number of lists) |
| 2021-04-17 13:01:03 | <freegraph> | Makes sense now, thanks! |
| 2021-04-17 13:02:03 | × | ridcully_ quits (~ridcully@pd951f269.dip0.t-ipconnect.de) (Quit: server update) |
| 2021-04-17 13:02:03 | <ski> | freegraph : now, if you have a function `foo', whose recursive case looks something like `foo (...) = foo (...) ++ stuff', then this will actually cause `(((...) ++ stuff2) ++ stuff1) ++ stuff0', left-associated, which is bad. similarly, if you have an accumulator, like 'foo (...) acc = foo (...) (acc ++ stuff)', this will cause a similar problem |
| 2021-04-17 13:02:47 | <ski> | while `foo (...) = stuff ++ foo (...)' or `foo (...) acc = foo (...) (stuff ++ acc)' won't have this left-associatedness problem |
All times are in UTC.