tag:blogger.com,1999:blog-3826164796564330590.post4299412896295927181..comments2016-11-15T17:06:14.927+02:00Comments on The Most Fuun You Can Have: Beautiful foldingQuizhttp://www.blogger.com/profile/01935712406320139010noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3826164796564330590.post-62974330468863496192008-11-16T21:04:00.000+02:002008-11-16T21:04:00.000+02:00Nice. One tiny thing I found confusing is your `af...Nice. <BR/><BR/>One tiny thing I found confusing is your `after` function <BR/><BR/>f . g reads like "f after g" <BR/><BR/>but in your case the code<BR/><BR/>after f g == f 'after' g is actually <BR/><BR/>"f before g" :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3826164796564330590.post-14733973193585466542008-11-11T19:58:00.000+02:002008-11-11T19:58:00.000+02:00BlackMeph: well, yeah, I thought that was kinda ob...BlackMeph: well, yeah, I thought that was kinda obvious. To find the mean of the first million primes you do indeed need to generate and traverse the list (unless there's some clever piece of number theory I don't know about...). But <I>in this specific case</I> there's a fantastic optimisation we can apply to give us constant-time performance, and it would be nice to be able to take advantage of it without sacrificing genericity.Mileshttp://www.blogger.com/profile/07136909835648629963noreply@blogger.comtag:blogger.com,1999:blog-3826164796564330590.post-19323616828230430002008-11-08T14:43:00.000+02:002008-11-08T14:43:00.000+02:00The reason this is not a problem in an imperative ...The reason this is not a problem in an imperative language, of course, is outside state - the counter can be trivially placed outside the loop.<BR/><BR/>This also, amusingly, makes it a good example to demonstrate that pure functions aren't the panacea of language design that FP aficionados make it out to be.FeepingCreaturehttp://www.blogger.com/profile/11949875328488880491noreply@blogger.comtag:blogger.com,1999:blog-3826164796564330590.post-89219721190220592502008-11-07T23:39:00.000+02:002008-11-07T23:39:00.000+02:00Sorry to butt in on your own blog, Quiz, but I wan...Sorry to butt in on your own blog, Quiz, but I wanted to mention something to miles (and feepingcreature indirectly):<BR/><BR/>The "range" isn't the tough part. Try doing it with the first million primes, for instance.<BR/><BR/>The main point is that if you want the geometric mean instead of the arithmetic, all the functions you need to change are easy to get to, from a conceptual point-of-view.BlackMephhttp://www.blogger.com/profile/02745499320156194052noreply@blogger.comtag:blogger.com,1999:blog-3826164796564330590.post-51136569733396418052008-11-07T23:04:00.000+02:002008-11-07T23:04:00.000+02:00Thank you all for your comments.FeepingCreature:Yo...Thank you all for your comments.<BR/><BR/>FeepingCreature:<BR/>Your D code is very much like my uglyMean, though one uses recursion and the other iteration. In Haskell, it's popular to abstract just about *everything*, including looping. The idea here is to abstract a loop that does multiple things with the same list.<BR/><BR/>Twan:<BR/>I did wonder if folds were an instance of an interesting typeclass, but never realised that they were Applicative. Thank you, I'll look into that.<BR/><BR/>Miles:<BR/>One option would be to make range types an instance of the Foldable typeclass, and use the more polymorphic Foldable.foldl' instead of List.foldl'.<BR/><BR/>Saizan:<BR/>Surprisingly, -funbox-strict-fields didn't make enough difference to mention.Quizhttp://www.blogger.com/profile/01935712406320139010noreply@blogger.comtag:blogger.com,1999:blog-3826164796564330590.post-46994564570885485622008-11-07T18:34:00.000+02:002008-11-07T18:34:00.000+02:00tried compiling with -funbox-strict-fields ? makin...tried compiling with -funbox-strict-fields ? making Fold's fields strict too perhapsSaizanhttp://www.blogger.com/profile/07314943153376710289noreply@blogger.comtag:blogger.com,1999:blog-3826164796564330590.post-87563081824976297942008-11-07T17:02:00.000+02:002008-11-07T17:02:00.000+02:00Nice!The thing that tickles me about this example,...Nice!<BR/><BR/>The thing that tickles me about this example, though, is that there's an obvious optimization for this particular benchmark: since the list we're taking the mean of is actually a range, we can calculate its sum using the well-known formula for the sum of an arithmetic progression, and its length by a simple subtraction and division - no traversals are required at all!<BR/><BR/>Now, I can see how to take advantage of this possibility automatically in object-oriented languages - make sum() and length() methods of your Enumerable class and override them in the Range class - but I can't see how to do this in functional languages without violating information hiding.Mileshttp://www.blogger.com/profile/07136909835648629963noreply@blogger.comtag:blogger.com,1999:blog-3826164796564330590.post-30664524825872275592008-11-07T14:25:00.000+02:002008-11-07T14:25:00.000+02:00Very interesting idea.The after combinator has (al...Very interesting idea.<BR/><BR/>The after combinator has (almost) the same type as fmap, so you could make Fold an instance of Functor:<BR/><BR/>> instance Functor (Fold a) where<BR/>> fmap = flip after<BR/><BR/>Similarly, your 'both' is like <*> from Applicative, so you could have an instance of that class as well:<BR/><BR/>> instance Applicative (Fold a) where<BR/>> pure x = (\_ _ -> ()) () (\_ -> x)<BR/>> f <*> g = uncurry <$> both f g<BR/>> -- or inline both/fmap in the above<BR/><BR/>Now you can write:<BR/><BR/>> meanF :: Fractional a => Fold a a<BR/>> meanF = (/) <$> sumF <*> (fromIntegral <$> lengthF)<BR/><BR/>Which is very close to what you can write in point free style using the standard Applicative instance for (e ->):<BR/><BR/>> mean :: Fractional a => [a] -> a<BR/>> mean = (/) <$> sum <*> (fromIntegral <$> length)Twan van Laarhovenhttp://www.blogger.com/profile/18138442561179666544noreply@blogger.comtag:blogger.com,1999:blog-3826164796564330590.post-36409223233762656452008-11-07T13:25:00.000+02:002008-11-07T13:25:00.000+02:00Meanwhile, for comparison, here's a straightforwar...Meanwhile, for comparison, here's <A HREF="http://paste.dprogramming.com/dpe3d7v5" REL="nofollow">a straightforward mean in an imperative language (D).</A>FeepingCreaturehttp://www.blogger.com/profile/11949875328488880491noreply@blogger.com