tag:blogger.com,1999:blog-4650294074444534066.post1104451234541062591..comments2014-09-01T19:15:42.442-07:00Comments on Typed Logic: A stream of primes as Comonadgeophfhttp://www.blogger.com/profile/09936874508556500234noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-4650294074444534066.post-25817900510362473602009-04-22T00:14:00.000-07:002009-04-22T00:14:00.000-07:00This comment has been removed by a blog administrator.xuemeihttp://www.blogger.com/profile/14932530347120263518noreply@blogger.comtag:blogger.com,1999:blog-4650294074444534066.post-12051025568089844482008-12-30T05:15:00.000-08:002008-12-30T05:15:00.000-08:00Your diff is wrong. The average of the list keep...Your diff is wrong. The average of the list keeps getting taken on a different list... i.e.<BR/><BR/>diff [1..10] <BR/><BR/>returns <BR/><BR/>[-4.5,-4.0 .. 0.0]<BR/><BR/>when it should return<BR/><BR/>[-4.5, -3.5 .. 4.5]<BR/><BR/>And how does expressing this computation comonadically help to eliminate extra passes of the list? I'll make two points:<BR/><BR/>1. Your incorrect implementation of "diff" makes many, many needless passes. ;-) It's quadratic in the length of the list when the real diff is linear. Even the incorrect version could be implemented linearly.<BR/><BR/>2. Laziness and tying-the-knot can indeed be employed, sometimes, to eliminate multiple passes of data. However, applying that techique to "diff", a la "Why Attribute Grammars Matter", is a red herring. That computation _cannot_ be done in a single pass. Period. <BR/><BR/>In that paper, the "optimized" version of diff builds a list of thunks, not Nums, making the second necessary pass implicit. Compiled with GHC -O, the "optimized" version (1 explicit pass + 1 implicit pass) takes basically the same amount of time as the naive version. (3 explicit passes.) <BR/><BR/>Moreover, the "optimized" version breaks GHC's list fusion scheme, whereas the naive version is a "good producer." (though not a good consumer.) Thus the optimized version can actually perform _worse_ than the naive version when inlined inside the right context. <BR/><BR/>You are much better off combining the two passes in the naive version of "avg" into a single pass, implementing "diff" as 2 explicit passes. This will actually speeds things up.<BR/><BR/>("Why Attribute Grammars Matter" is an ok paper, probably worth reading. But that example is bad and my feeling is that it doesn't really make it's case of why they matter as a result.)<BR/><BR/>I'd love to see a comonadic version of diff, with the optimizations needed to reduce the number of passes to 2.Leon Smithhttp://www.blogger.com/profile/06462854866941248768noreply@blogger.comtag:blogger.com,1999:blog-4650294074444534066.post-26246698990831913332008-09-03T09:02:00.000-07:002008-09-03T09:02:00.000-07:00For comparison, and to demonstrate how this works ...For comparison, and to demonstrate how this works in the imperative D language, of which I am a fanboy:<BR/><BR/>// difference of values from average<BR/>// works with any kind of collection<BR/>ElemType!(T)[] diff_avg(T)(T inp) {<BR/>__auto res = new ElemType!(T)[inp.length];<BR/>__real avg = 0.0;<BR/>__foreach (v; inp) avg += v;<BR/>__avg /= inp.length;<BR/>__foreach (i, v; inp) res[i] = abs(v - avg);<BR/>__return res;<BR/>}<BR/><BR/>And to define a stream of primes:<BR/><BR/>int delegate() primes() {<BR/>__return stuple([2], 3) /apply/ (ref int[] primes, ref int current) {<BR/>____while (true) {<BR/>______scope(exit)<BR/>________current ++;<BR/>______auto limit = cast(int) (sqrt(current) + 1);<BR/>______bool found;<BR/>______foreach (prime; primes) {<BR/>________if (prime > limit) break;<BR/>________if (current % prime == 0) {<BR/>__________found = true; break;<BR/>________}<BR/>______}<BR/>______if (found) continue;<BR/>______primes ~= current;<BR/>______return current;<BR/>____}<BR/>__};<BR/>}<BR/><BR/>A bit longer, I guess, but not that much.<BR/><BR/>Sorry for the strange indentation. It appears Blogger lacks a code tag.<BR/><BR/> --feepFeepingCreaturehttp://www.blogger.com/profile/11949875328488880491noreply@blogger.com