tag:blogger.com,1999:blog-11295132.post4999062346864102325..comments2014-06-25T07:05:59.204-07:00Comments on A Neighborhood of Infinity: Types, and two approaches to problem solvingDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-11295132.post-69810130919687676802014-05-17T12:58:50.345-07:002014-05-17T12:58:50.345-07:00The intro reminded me of a recent post on cstheory...The intro reminded me of a recent post on cstheory, http://cstheory.stackexchange.com/questions/22578/would-it-be-possible-for-a-compiler-to-convert-a-recursive-sum-into-the-average<br /><br />The post could be cleaned up, but it asks an interesting question as to if a compiler could recognize and translate between various recursive formulas for the triangular numbers.<br /> <br />$T_{a+b} = T_a + T_b + ab$, addition recursion<br /><br />$T_{ab} = T_aT_b + T_{a-1}T_{b-1}$, quotient recursionChad Brewbakerhttp://www.blogger.com/profile/10443154815748267611noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-60323998046497282632014-05-17T10:04:12.569-07:002014-05-17T10:04:12.569-07:00@quiz If you partition any set into a bunch of sub...@quiz If you partition any set into a bunch of subsets then you have two ways of looking at the situation. You can think of the subsets as being *sub*sets. But you can think of the collection of subsets itself as being a quotient set. So you can move back and forth between the two views.<br /><br />A Galois connection (http://en.wikipedia.org/wiki/Galois_connection) is also something that allows you to go back and forth between quotient and sub- things. (That article also mentions abstract interpretation.)<br /><br />So to some extent it's a point of view. But in different contexts one or other view can seem more natural.Dan Piponihttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-48176641910280422872014-05-17T09:31:34.813-07:002014-05-17T09:31:34.813-07:00I think you could argue that the partition step of...I think you could argue that the partition step of quicksort is a quotienty algorithm: to sort xs, we take the quotient of less-or-greater-than-pivot, and sort in the quotient. Compare to merge sort, which does the division into subproblems as the first step.Quizhttp://www.blogger.com/profile/01935712406320139010noreply@blogger.com