tag:blogger.com,1999:blog-1777990983847811806.post6076362602472105059..comments2022-01-16T11:12:19.370-08:00Comments on Haskell for all: Composable streaming foldsGabriella Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-1777990983847811806.post-6928006215481292412021-03-14T04:51:58.370-07:002021-03-14T04:51:58.370-07:00The key point is that every monoid provides an int...The key point is that every monoid provides an interpretation of the free monoid of its underlying set. that's the counit of the free/forgetful adjunction Free |M| -> M.<br /><br />This morphism is computed using the universal property of lists [a] = mu x. 1 + a * x , and the specific algebra provided at a by the monoid structure (1 + a * a) -> a. Nicolashttps://www.blogger.com/profile/03434148024010872285noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-63746823840431405522016-05-28T09:57:11.579-07:002016-05-28T09:57:11.579-07:00Yeah, I also created a package for the left-fold v...Yeah, I also created a package for the left-fold variation of this trick: http://hackage.haskell.org/package/foldlGabriella Gonzalezhttps://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-84689023036541030162016-05-26T23:20:33.458-07:002016-05-26T23:20:33.458-07:00This might be relevant: https://hackage.haskell.or...This might be relevant: https://hackage.haskell.org/package/foldsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-21862257888842931032014-08-14T09:09:46.875-07:002014-08-14T09:09:46.875-07:00I don't know what discussion went into it, but...I don't know what discussion went into it, but since that decision was made, Edward Kmett at least has used it for lazy Nats. The rewrite rules were an attempt to imrove efficiency in some cases, bu in my opinion were poorly conceived.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-841728947483190492014-08-13T06:40:45.399-07:002014-08-13T06:40:45.399-07:00Huh, I never realized that. Is there any mailing ...Huh, I never realized that. Is there any mailing list thread documenting why they chose to implement it that way?Gabriella Gonzalezhttps://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-8837383652274452552014-08-13T01:45:46.547-07:002014-08-13T01:45:46.547-07:00The situation with Data.List.genericLength is much...The situation with Data.List.genericLength is much messier than you describe. In fact, if you add one or two zeros to your first example, ghci will run out of stack space, but code compiled with -O will not. This is because genericLength is lazy by default (essentially written as a right fold), but has special rewrite rules for Integer and Int to make it (essentially) a strict left fold. So in optimized code, the defaulting to Integer makes that work okay, but as soon as you divide by *anything*, even a fixed constant like 2, the default turns to Double, which doesn't have that exception, and memory usage goes through the roof.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-87528975231655745262013-08-13T20:22:26.700-07:002013-08-13T20:22:26.700-07:00Yeah, you are right. That makes much more sense. ...Yeah, you are right. That makes much more sense. I will fix this.Gabriella Gonzalezhttps://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-25659351544511378122013-08-13T20:19:48.297-07:002013-08-13T20:19:48.297-07:00Shouldn't a more generic version use whatever ...Shouldn't a more generic version use whatever the result type is rather than Integer, which is horrifically slow? (Say were I working with Word64.)Anonymoushttps://www.blogger.com/profile/00849067796909388609noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-12988624366350422932013-08-06T10:25:27.504-07:002013-08-06T10:25:27.504-07:00I skimmed it before but I read it more closely thi...I skimmed it before but I read it more closely this time. I see what you mean now. My proposal is a special case of their using `Const` to fold and `Prod` to combine multiple folds (although it would need to be a strict `Prod`).<br /><br />The main advantage to specializing it just to folds is that you get the nice `Applicative` instance for `Fold`, which you don't get if you use `Const` and `Prod` unless you formulated some sort of higher-order `Applicative`.<br /><br />There is also a performance advantage if you stick to strict left folds. I've been writing this up here:<br /><br />https://github.com/Gabriel439/Haskell-Foldl-Library/blob/master/src/Control/Foldl.hs<br /><br />... and if you use the "free left fold" approach you get much better core, and it gets even better once you start adding rewrite rules to fuse away the intermediate list.Gabriella Gonzalezhttps://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-69927765883168861892013-08-06T08:42:30.859-07:002013-08-06T08:42:30.859-07:00Have you looked at the paper "The essence of ...Have you looked at the paper "The essence of iteration", Gabriel?<br />=> www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf<br /><br />I think the authors have the same objective. For me, this paper was very enlightening as to the understanding of the interests of Applicatives.Anonymoushttps://www.blogger.com/profile/11382268504770604242noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-72064098705264712112013-08-04T13:51:54.908-07:002013-08-04T13:51:54.908-07:00So I just tested it and your version produces stri...So I just tested it and your version produces strikingly more efficient code. It also solves a problem that the `Monoid`-based version does not, which is that you encode strict left fold using your version, whereas the `Monoid`-based approach cannot (while still running in constant space).<br /><br />So I'm going to switch to your way.Gabriella Gonzalezhttps://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-19618069005556603702013-08-04T09:18:39.678-07:002013-08-04T09:18:39.678-07:00I forgot to answer the second half of your questio...I forgot to answer the second half of your question: the constraint does not give you extra power. See this post by Brent Yorgey which explains how foldMap and foldr are equivalent:<br /><br />http://byorgey.wordpress.com/2012/11/05/foldr-is-made-of-monoids/Gabriella Gonzalezhttps://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-83586975704181806452013-08-04T09:02:44.533-07:002013-08-04T09:02:44.533-07:00I arrived at this from simplifying some `pipes` fo...I arrived at this from simplifying some `pipes` folding code that used `WriterT` in the base monad, so the original code had to use the `Monoid`-based approach. It's just a legacy of how I originally arrived at the problem.<br /><br />I will probably write this up into a library soon and I will benchmark both approaches, too, and use the one that produces more efficient code.Gabriella Gonzalezhttps://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-24879386967453330092013-08-04T09:00:13.452-07:002013-08-04T09:00:13.452-07:00For some weird reason I thought that you needed a ...For some weird reason I thought that you needed a case statement to unpack an existentially quantified data type. Even weirder, I somehow got it right on the `Functor` instance without even realizing what I was doing.<br /><br />Thanks for pointing this out! I fixed that and the Applicative instance as well.Gabriella Gonzalezhttps://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-40485853984841687542013-08-04T08:57:48.812-07:002013-08-04T08:57:48.812-07:00Yeah, you're right. I fixed it.Yeah, you're right. I fixed it.Gabriella Gonzalezhttps://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-30792994882931604922013-08-04T08:52:50.765-07:002013-08-04T08:52:50.765-07:00Yes, it should. I used `Int` for efficiency but t...Yes, it should. I used `Int` for efficiency but then forgot that this completely defeats the purpose of `genericLength`. I will fix it.Gabriella Gonzalezhttps://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-24877392894843951672013-08-04T07:40:34.981-07:002013-08-04T07:40:34.981-07:00Great article! I'm appreciating Applicative mo...Great article! I'm appreciating Applicative more and more each day.Mikhail Glushenkovhttps://www.blogger.com/profile/16766775468165268210noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-21453689188756693092013-08-04T05:32:55.932-07:002013-08-04T05:32:55.932-07:00The monoid constraint facilitates composition, and...The monoid constraint facilitates composition, and adds convenience (mempty is used implicitly rather than providing the start value explicitly). You could accomplish the same compositional capabilities without Monoid.Dan Burtonhttps://www.blogger.com/profile/05271453123975117703noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-15663103767560296692013-08-04T03:53:58.663-07:002013-08-04T03:53:58.663-07:00In my formulation of this technique (http://squing...In my formulation of this technique (http://squing.blogspot.com/2008/11/beautiful-folding.html), there is no Monoid constraint on the accumulator technique. Does the constraint give you any extra power?Quizhttps://www.blogger.com/profile/01935712406320139010noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-77996006222221953742013-08-04T03:16:50.041-07:002013-08-04T03:16:50.041-07:00`average = (/) <$> sum <*> length`
sh...`average = (/) <$> sum <*> length`<br /><br />should it be<br /><br />`average = (/) <$> sum <*> genericLength`<br /><br />?<br /><br />Anonymoushttps://www.blogger.com/profile/08350661551275657152noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-3748154806883363382013-08-04T03:08:10.292-07:002013-08-04T03:08:10.292-07:00`fold f xs = case f of
Fold t c -> c (fold...`fold f xs = case f of <br /> Fold t c -> c (foldl' mappend mempty (map t xs))`<br /><br />why not <br />`fold (Fold t c) xs = c (foldl' mappend mempty (map t xs))`Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-49958591966060477692013-08-04T00:33:49.158-07:002013-08-04T00:33:49.158-07:00Great article!
Shouldn't the genericLength us...Great article!<br /><br />Shouldn't the genericLength use Integer instead of Int in the Sum monoid to avoid possible overflow, though?Kari Oikarinennoreply@blogger.com