tag:blogger.com,1999:blog-13960885.post7707165654882834160..comments2017-06-26T17:05:53.144-07:00Comments on C++ Truths: Folding FunctionsSumant Tambehttps://plus.google.com/117220997561739301261noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-13960885.post-66683303344419821272017-06-14T05:37:27.102-07:002017-06-14T05:37:27.102-07:00Yes, that is a right category theoretic interpreta...Yes, that is a right category theoretic interpretation. I don't know if it is standard to interpret the object in the category as the "type" of the functions though (even if it is the domain and codomain of the morphisms), as in other kind of monoids the object could be basically anything as long as the morphisms are the objects of the monoid and composition is defined the same way as the operation. I'll explain a bit better:<br /><br />Consider natural numbers (with zero) with addition. As long as you define the morphisms over the object to be the natural numbers, being the identity zero, and the composition of morphisms is the defined as addition, the object could be anything. So, in some examples, the object might mean nothing, only providing the structure to the monoid.<br /><br />But yes, in this case, at least to me, that sounds like a quite good interpretation of the category theoretic definition. In fact, it makes easy to understand the definitions of category functor (https://en.wikipedia.org/wiki/Functor) and functional programming functor.<br /><br />You're welcome :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-13960885.post-46031290708363240612017-06-13T22:25:03.071-07:002017-06-13T22:25:03.071-07:00Ok. I understand your comment much better now. I w...Ok. I understand your comment much better now. I was wondering for a while why you said "defined" as opposed to equal or something like that in the original comment. But I assumed a bit about what you might have meant. <br /><br />Yeah, it turns out composition of functions as a monoid is fairly restrictive as the domain and codomain of the functions must be the type. Even single-argument-single-return-value functions are quite restrictive in imperative general-purpose languages. Currying is not practical in most such languages. <br /><br />So is the following a correct from a category theoretic interpretation?<br />1. The "only object" in the monoid of function composition is the "type" of the functions, which has same domain and codomain types. <br />2. Each function in the family would be a morphism. Again all of them have the same type and their domain and codomain are the same.<br />3. Composition of any two yields another function, which is also a morphism. <br /><br />Does this make sense? <br /><br />Thanks much for providing feedback and helping me arrive at the right understanding.Sumant Tambehttp://www.blogger.com/profile/11957855386259543653noreply@blogger.comtag:blogger.com,1999:blog-13960885.post-33998380446729679742017-06-12T10:37:14.219-07:002017-06-12T10:37:14.219-07:00No. I'm referring exactly to the concept of mo...No. I'm referring exactly to the concept of monoid. I didn't say that a b should equal b a, I said that both a b and b a should be defined. In the case of functions with function composition, if they don't have the same domain and codomain, you can easily find the case where a b is defined but b a is not.<br /><br />Moreover, if you're into functional programming, I might better explain this using the (equivalent) category theoretic definition of monoid: a monoid is defined as a category with only one object, in which the elements of the monoid in the classical definition correspond to the morphisms over the object and the operation corresponds to the composition of morphisms (note that in this case, the domain and codomain of all morphisms is trivially the same).<br /><br />You can see https://en.wikipedia.org/wiki/Monoid#Definition for the classic definition,<br />and https://en.wikipedia.org/wiki/Monoid#Relation_to_category_theory for the category theoretic definition.<br /><br />By the way, I have quite liked this series of posts, I'd love to see more people building functional programming abstractions in C++.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-13960885.post-57596022775226812502017-06-04T02:13:02.194-07:002017-06-04T02:13:02.194-07:00@Anonymous I don't think that's the case. ...@Anonymous I don't think that's the case. I think you are referring to commutative monoids, where a b = b a. A general monoid does not have that restriction. Please see http://mathworld.wolfram.com/CommutativeMonoid.htmlSumant Tambehttp://www.blogger.com/profile/11957855386259543653noreply@blogger.comtag:blogger.com,1999:blog-13960885.post-64930532797526585602017-06-02T16:06:00.405-07:002017-06-02T16:06:00.405-07:00If you look at the definition of monoid, you'l...If you look at the definition of monoid, you'll realize that it is defined as a set with a binary operation satisfying certain conditions. That is, for every a,b in the set, a `op` b (and also b `op` a) is defined. If your chosen operation (composition in this case) doesn't satisfy this, you cannot say you have a monoid.<br /><br />If it isn't clear enough: even if is_even composes with to_num, you still need to_num to compose with is_even, as an absolute requirement.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-13960885.post-11002585960681418802017-01-03T05:27:43.969-08:002017-01-03T05:27:43.969-08:00I believe an attribution to this article would be ...I believe an attribution to this article would be in order https://ngathanasiou.wordpress.com/2016/11/23/compose-and-curry-as-folds/ . Composition as folding with the function call operator is not that common and what's presented here is pretty much described in the linked article. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-13960885.post-58722553630933478742016-12-30T14:32:25.396-08:002016-12-30T14:32:25.396-08:00@Sandeep Thanks. The statement appears "loade...@Sandeep Thanks. The statement appears "loaded" only if someone is unfamiliar to the concept of monoid. It's not true that functions form a monoid only when they have the same domain and range. The example functions to_num has string domain and int range. is_even has int domain and bool range. So they are clearly not the same. If you are referring to the fact that range of the first function needs to line up with domain of the next then you are talking about the composition operation. composition operation is itself illegal when that condition is not satisfied. Then the whole point is moot. Assuming function composition requirement is satisfied, what else can we say about function composition. Well, such functions form a monoid.<br /><br />@Anonymous Here's the link: http://stackoverflow.com/questions/2562320/specializing-a-template-on-a-lambda-in-c0x/2565037#2565037Sumant Tambehttp://www.blogger.com/profile/11957855386259543653noreply@blogger.comtag:blogger.com,1999:blog-13960885.post-16790508994313312412016-12-29T21:41:56.900-08:002016-12-29T21:41:56.900-08:00"I'll skip the implementation of the deta..."I'll skip the implementation of the detail namespace. It's in the same vein as this stackoverflow answer. "<br /><br />There is no link to the relevant stackoverflow post. Could you update this?<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-13960885.post-40498009884387377362016-12-29T14:47:07.725-08:002016-12-29T14:47:07.725-08:00Nice post.
I think the last statement about funct...Nice post.<br /><br />I think the last statement about function composition being a monaid is a bit loaded though. It is a monoid only if the functions have the same domain and range.<br /><br />> As std::function is kind of verbose and not very idiomatic in C++ when you want to pass functions around<br /><br />As someone from C++ background, this is very true. Since functions are not first class citizens, a concept/pattern involving functions is hard to highlight in C++. Sandeep. http://www.blogger.com/profile/02145858882098955679noreply@blogger.com