Logs: liberachat/#haskell
| 2021-07-14 19:09:42 | × | azeem quits (~azeem@dynamic-adsl-84-220-239-177.clienti.tiscali.it) (Read error: Connection reset by peer) |
| 2021-07-14 19:09:47 | <burnsidesLlama> | Yes! I meant the lifted versions |
| 2021-07-14 19:09:54 | × | favonia quits (~favonia@user/favonia) (Ping timeout: 255 seconds) |
| 2021-07-14 19:10:32 | → | azeem joins (~azeem@dynamic-adsl-84-220-239-177.clienti.tiscali.it) |
| 2021-07-14 19:10:57 | → | cheater1__ joins (~Username@user/cheater) |
| 2021-07-14 19:11:11 | × | cheater quits (~Username@user/cheater) (Ping timeout: 268 seconds) |
| 2021-07-14 19:11:20 | cheater1__ | is now known as cheater |
| 2021-07-14 19:11:33 | <dminuoso> | burnsidesLlama: At any rate. tails seems like a far better choice |
| 2021-07-14 19:12:01 | <dminuoso> | Well. "better" is a poor qualifier |
| 2021-07-14 19:12:20 | <dminuoso> | tails has better asymptotics |
| 2021-07-14 19:13:19 | × | drd quits (~drd@2001:b07:a70:9f1f:1562:34de:f50f:77d4) (Ping timeout: 268 seconds) |
| 2021-07-14 19:14:10 | × | zeenk quits (~zeenk@2a02:2f04:a106:9600:82fb:aed9:ca9:38d3) (Quit: Konversation terminated!) |
| 2021-07-14 19:14:39 | <burnsidesLlama> | I don't tails has better asymptotics. inits returns initial segments in increasing length order. It can be implemented as "inits [] = [], inits (x:xs) = [] : map (x:) (inits xs)" |
| 2021-07-14 19:15:18 | <zzz> | hlint: Unnecessary hiding, why not romove it? |
| 2021-07-14 19:15:20 | zzz | removes it |
| 2021-07-14 19:15:50 | <zzz> | ghc: Error: Ambiguous occurrence |
| 2021-07-14 19:16:07 | <dminuoso> | burnsidesLlama: Mmm. So it seems my information is just out-of-date here |
| 2021-07-14 19:16:22 | <dminuoso> | You cant implement inits naively if you ever expect fusion to occur. |
| 2021-07-14 19:16:37 | × | myShoggoth quits (~myShoggot@97-120-70-214.ptld.qwest.net) (Read error: Connection reset by peer) |
| 2021-07-14 19:16:40 | <dminuoso> | Which is why the current version is implemented as: inits = map toListSB . scanl' snocSB emptySB |
| 2021-07-14 19:16:55 | → | myShoggoth joins (~myShoggot@97-120-70-214.ptld.qwest.net) |
| 2021-07-14 19:18:24 | → | jippiedoe joins (~david@77-171-152-62.fixed.kpn.net) |
| 2021-07-14 19:19:14 | <[exa]> | burnsidesLlama: maybe bad question, but why not instead generalize the easier "flipped" direction, i.e., [1,2,3] -> [0, 1+0, 2+1+0, 3+2+1+0] |
| 2021-07-14 19:19:49 | <burnsidesLlama> | dminuoso I wasn't looking at the source earlier. What do you mean 'if you ever expect fusion to occur?', the source says something technical about consumers and producers |
| 2021-07-14 19:20:19 | <[exa]> | burnsidesLlama: ah I re-read your question now. :D |
| 2021-07-14 19:20:27 | → | merijn joins (~merijn@83-160-49-249.ip.xs4all.nl) |
| 2021-07-14 19:21:03 | <dminuoso> | burnsidesLlama: See https://gitlab.haskell.org/ghc/ghc/-/issues/9345 |
| 2021-07-14 19:21:12 | <[exa]> | burnsidesLlama: you can easily convert this "flipped" one to the other, but IMO not vice versa because the "unflipped" way requires some way of counting stuff. |
| 2021-07-14 19:21:21 | → | drd joins (~drd@93-39-151-19.ip76.fastwebnet.it) |
| 2021-07-14 19:21:24 | → | qbt joins (~edun@user/edun) |
| 2021-07-14 19:21:40 | <dminuoso> | [exa]: This one doesnt work for infinite lists. :( |
| 2021-07-14 19:22:28 | → | cheater1__ joins (~Username@user/cheater) |
| 2021-07-14 19:22:32 | → | favonia joins (~favonia@user/favonia) |
| 2021-07-14 19:22:35 | <burnsidesLlama> | irc question, how do you reference someone's name like you two have been doing? |
| 2021-07-14 19:22:38 | × | cheater quits (~Username@user/cheater) (Ping timeout: 272 seconds) |
| 2021-07-14 19:22:41 | cheater1__ | is now known as cheater |
| 2021-07-14 19:22:54 | <zzz> | burnsidesLlama: depends on your client, most have autocomplete |
| 2021-07-14 19:22:59 | <EvanR> | i type the first few letters and hit tab |
| 2021-07-14 19:23:14 | <burnsidesLlama> | EvanR: This works for me :) |
| 2021-07-14 19:24:13 | <dminuoso> | burnsidesLlama: So in simplified terms, GHC employs an optimization called short cut fusion |
| 2021-07-14 19:24:39 | <dminuoso> | As an example, by law it's obvious that `fmap f . fmap g = fmap (f . g)` |
| 2021-07-14 19:24:40 | × | qbt quits (~edun@user/edun) (Client Quit) |
| 2021-07-14 19:24:53 | <burnsidesLlama> | [exa]: I suspect the flipped direction is natural for 'snoc' lists. I think there are four functions of the style of init and tails, which come in two pairs. One pair is natural for cons lists, and one is natural for snoc lists. I think the snoc list ones are 'tails' in increasing length order, and 'inits' in decreasing length order |
| 2021-07-14 19:24:54 | <dminuoso> | The latter generally performs better, because it avoids the intermediate data structure |
| 2021-07-14 19:25:12 | × | MQ-17J quits (~MQ-17J@8.21.10.15) (Ping timeout: 255 seconds) |
| 2021-07-14 19:25:38 | <dminuoso> | And short cut fusion gives GHC a way of avoiding intermediate data structures behind the scenes. |
| 2021-07-14 19:25:50 | × | merijn quits (~merijn@83-160-49-249.ip.xs4all.nl) (Ping timeout: 255 seconds) |
| 2021-07-14 19:26:10 | <burnsidesLlama> | dminuoso: So GHC automatically applies fusion laws of various kinds for optimisation (e.g. fold fusion, the map fusion you just mentioned)? |
| 2021-07-14 19:27:12 | <dminuoso> | It only does so under particular circumstances |
| 2021-07-14 19:27:28 | → | MQ-17J joins (~MQ-17J@d14-69-206-129.try.wideopenwest.com) |
| 2021-07-14 19:27:57 | <dminuoso> | A particular example is that sum [0...10] does not actually require a list data type in the first place. |
| 2021-07-14 19:28:33 | <dminuoso> | For that to work, the list has to be constructed specially in a way that this fusion can fire |
| 2021-07-14 19:28:46 | → | cfricke joins (~cfricke@user/cfricke) |
| 2021-07-14 19:29:04 | <dminuoso> | It roughly works like this: |
| 2021-07-14 19:29:10 | → | qbt joins (~edun@user/edun) |
| 2021-07-14 19:29:18 | <dminuoso> | build :: forall a . (forall b . (a -> b -> b) -> b -> b) -> [a] |
| 2021-07-14 19:29:56 | <dminuoso> | This is a way to construct lists, if you notice closely, it's a sort of "turned around foldr" |
| 2021-07-14 19:29:58 | <dminuoso> | % :t foldr |
| 2021-07-14 19:29:59 | <yahb> | dminuoso: forall {t :: * -> *} {a} {b}. Foldable t => (a -> b -> b) -> b -> t a -> b |
| 2021-07-14 19:30:34 | <dminuoso> | So GHC comes with special rewrite rules, that if you foldr right after build, they cancel each other out - and you dont have any intermedaite cons cells |
| 2021-07-14 19:30:52 | × | koolazer quits (~koo@user/koolazer) (Ping timeout: 272 seconds) |
| 2021-07-14 19:30:58 | × | qbt quits (~edun@user/edun) (Client Quit) |
| 2021-07-14 19:31:24 | × | norias quits (~jaredm@c-98-219-195-163.hsd1.pa.comcast.net) (Ping timeout: 252 seconds) |
| 2021-07-14 19:31:49 | <dminuoso> | Instead what you end up with is just a loop |
| 2021-07-14 19:33:22 | → | qbt joins (~edun@user/edun) |
| 2021-07-14 19:34:50 | × | cheater quits (~Username@user/cheater) (Ping timeout: 255 seconds) |
| 2021-07-14 19:35:01 | → | cheater joins (~Username@user/cheater) |
| 2021-07-14 19:35:24 | × | qbt quits (~edun@user/edun) (Client Quit) |
| 2021-07-14 19:36:50 | <burnsidesLlama> | dminuoso: I don't understand the type signature of build. Why is it not build :: ((a -> [a] -> [a]) -> [a] -> [a]) -> [a]? What are the foralls doing? |
| 2021-07-14 19:37:09 | × | alinab_ quits (sid468903@id-468903.brockwell.irccloud.com) () |
| 2021-07-14 19:37:21 | → | alinab_ joins (sid468903@id-468903.brockwell.irccloud.com) |
| 2021-07-14 19:37:43 | → | norias joins (~jaredm@c-98-219-195-163.hsd1.pa.comcast.net) |
| 2021-07-14 19:37:50 | <dminuoso> | build g = g (:) [] |
| 2021-07-14 19:37:51 | alinab_ | is now known as alinab |
| 2021-07-14 19:37:57 | → | qbt joins (~edun@user/edun) |
| 2021-07-14 19:38:25 | <burnsidesLlama> | Related question, how does build build lists? E.g. how might we write sum using build and fold? |
| 2021-07-14 19:41:05 | → | burnside_ joins (~burnsides@dhcp168-025.wadham.ox.ac.uk) |
| 2021-07-14 19:41:05 | × | burnsidesLlama quits (~burnsides@dhcp168-025.wadham.ox.ac.uk) (Read error: Connection reset by peer) |
| 2021-07-14 19:41:38 | → | burnsidesLlama joins (~burnsides@dhcp168-025.wadham.ox.ac.uk) |
| 2021-07-14 19:41:38 | <burnsidesLlama> | https://wiki.haskell.org/Correctness_of_short_cut_fusion seems like it has the answers for my fusion related questions. Thanks :) |
| 2021-07-14 19:41:38 | × | burnside_ quits (~burnsides@dhcp168-025.wadham.ox.ac.uk) (Read error: Connection reset by peer) |
| 2021-07-14 19:42:12 | × | qbt quits (~edun@user/edun) (Ping timeout: 245 seconds) |
| 2021-07-14 19:42:47 | × | eggplantade quits (~Eggplanta@108-201-191-115.lightspeed.sntcca.sbcglobal.net) (Remote host closed the connection) |
| 2021-07-14 19:42:48 | × | burnsidesLlama quits (~burnsides@dhcp168-025.wadham.ox.ac.uk) (Read error: Connection reset by peer) |
| 2021-07-14 19:42:54 | → | burnsidesLlama joins (~burnsides@dhcp168-025.wadham.ox.ac.uk) |
| 2021-07-14 19:43:01 | → | P1RATEZ joins (piratez@user/p1ratez) |
| 2021-07-14 19:43:33 | → | eggplantade joins (~Eggplanta@108-201-191-115.lightspeed.sntcca.sbcglobal.net) |
| 2021-07-14 19:43:52 | × | eggplantade quits (~Eggplanta@108-201-191-115.lightspeed.sntcca.sbcglobal.net) (Remote host closed the connection) |
| 2021-07-14 19:44:01 | × | eight quits (~eight@user/eight) (Quit: leaving) |
| 2021-07-14 19:44:58 | <dminuoso> | burnsidesLlama: Try and understand how this works: |
| 2021-07-14 19:45:04 | <dminuoso> | % foldr (:) [] [1,2,3] |
| 2021-07-14 19:45:05 | <yahb> | dminuoso: [1,2,3] |
| 2021-07-14 19:45:12 | <dminuoso> | If you do, you should be able to grok `build` |
| 2021-07-14 19:45:43 | × | Obo quits (~roberto@70.pool90-171-81.dynamic.orange.es) (Ping timeout: 268 seconds) |
| 2021-07-14 19:45:44 | <dminuoso> | (The key idea is simply, that a list can be thought of as an arbitrary fold with (:) and [] plucked in) |
| 2021-07-14 19:46:25 | → | qbt joins (~edun@user/edun) |
| 2021-07-14 19:46:30 | <burnsidesLlama> | Yes, we are replacing the (:) and [] in a list expression with (:) and [] respectively |
| 2021-07-14 19:46:54 | <dminuoso> | Sure, and now imagine it doesnt even matter whether the original is a list or not. |
| 2021-07-14 19:47:25 | <dminuoso> | Could be a tree for all we know |
| 2021-07-14 19:48:12 | → | Guest9 joins (~Guest9@43.250.157.35) |
All times are in UTC.