tag:blogger.com,1999:blog-11295132.post4017097209254768099..comments2014-06-25T07:05:59.204-07:00Comments on A Neighborhood of Infinity: Categories of polynomials and comonadic plumbingDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger23125tag:blogger.com,1999:blog-11295132.post-68770027923055309042008-07-18T18:54:00.000-07:002008-07-18T18:54:00.000-07:00Dan, Edward, thank you for the explanation; it ma...Dan, Edward, thank you for the explanation; it makes sense now.Piet Delporthttp://www.blogger.com/profile/04448807080922727437noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-15691029426643678372008-07-03T08:21:00.000-07:002008-07-03T08:21:00.000-07:00Sorry about that. I forgot the context of the arti...Sorry about that. I forgot the context of the article. It has been long enough that this thread has kind of taken on a life of its own. =)Edward Kmetthttp://www.blogger.com/profile/16144424873202502715noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-62333052169583940902008-07-03T08:05:00.000-07:002008-07-03T08:05:00.000-07:00Edward,I did mention that I was dealing with a sub...Edward,<BR/><BR/>I did mention that I was dealing with a subset of Haskell that allows only total functions. It's messy otherwise.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-50626051177881093042008-07-03T04:55:00.000-07:002008-07-03T04:55:00.000-07:00() has two inhabitants _|_ and (), so there are mu...() has two inhabitants _|_ and (), so there are multiple functions from a -> () the moment you allow recursion, which causes () to fail to be terminal.<BR/><BR/>Also because Haskell is not total you need to be careful, since <BR/><BR/>data Void <BR/><BR/>has a single inhabitant _|_ and satisfies (most of) the conditions for a terminal object.<BR/><BR/>Of course all of this is a pleasant fiction because in the presence of seq you can even distinguish some inhabitants of a -> _|_. But if we ignore seq we get nice properties.<BR/><BR/>Unfortunately, since _|_ is an inhabitant of every type in Haskell, there is no initial object in Hask. <BR/><BR/>One way to see Void is not initial is to see that there is no uniqueness to the function from Void -> a for each a in Haskell. you are free to choose any inhabitant of a, each giving rise to another morphism in the category. The uniqueness constraint is violated. If we were strict then we might be able to say that the only member of that type was a function returning _|_.<BR/><BR/>Another way to look at it: for Hask to be comonoidal there would have to be a type Void for which 'Either Void a' can only contain 'Right a's since you can have 'Left _|_'s. This prevents the category of Haskell types from being CoCartesian. <BR/><BR/>This is why in category-extras this constraint is captured by saying Hask is pre-(co-Cartesian closed).Edward Kmetthttp://www.blogger.com/profile/16144424873202502715noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-50952213240546891942008-07-03T03:08:00.000-07:002008-07-03T03:08:00.000-07:00Piet,1 is definitely terminal, there's always a ma...Piet,<BR/><BR/>1 is definitely terminal, there's always a map from X to 1 defined (in Haskell) by<BR/><BR/>const () :: a -> ()<BR/><BR/>0, or the 'empty' type defined by the (extended) Haskell<BR/><BR/>data Void<BR/><BR/>is initial.<BR/><BR/>'Elements' of objects X can be picked out using maps from the terminal object to X. So in Set maps 1->X are the same as elements of X.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-56765079059304017952008-07-02T02:59:00.000-07:002008-07-02T02:59:00.000-07:00"[...] introduce the function x:1->A where 1 is th..."[...] introduce the function x:1->A where 1 is the terminal object in Hask, normally called ()."<BR/><BR/>s/terminal/initial/ ?Piet Delporthttp://www.blogger.com/profile/04448807080922727437noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-2491744616277733032008-06-26T06:29:00.000-07:002008-06-26T06:29:00.000-07:00sigfpe, FYI, the link to wikipedia for Ring seems ...sigfpe, FYI, the link to wikipedia for Ring seems to be broken. The link on your blog currently points to ...<BR/><BR/>http://sigfpe.blogspot.com/%E2%80%9Dhttp://en.wikipedia.org/wiki/Ring_%28mathematics%29%E2%80%9D<BR/><BR/>... which doesn't seem to work. The link to Ring in wikipedia that does work is the following:<BR/><BR/>http://en.wikipedia.org/wiki/Ring_(mathematics)geophfhttp://www.blogger.com/profile/09936874508556500234noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-76088236971204095672008-06-26T06:26:00.000-07:002008-06-26T06:26:00.000-07:00sigfpe, the link to Wikipedia for rings seems to b...sigfpe, the link to Wikipedia for rings seems to be broken. The link that I got working is the following:<BR/><BR/>http://en.wikipedia.org/wiki/Ring_(mathematics)<BR/><BR/>... but the link on the blog entry is currently ...<BR/><BR/>http://sigfpe.blogspot.com/%E2%80%9Dhttp://en.wikipedia.org/wiki/Ring_%28mathematics%29%E2%80%9D<BR/><BR/>... which seems not to workgeophfhttp://www.blogger.com/profile/09936874508556500234noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-52597183272038514032008-06-25T08:01:00.000-07:002008-06-25T08:01:00.000-07:00Off-topic, Dan, but would you have any opinion on ...Off-topic, Dan, but would you have any opinion on Dorst/Mann's use of geometric algebra to present a unified view of ray-tracing?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-6067111465081793252008-06-22T11:36:00.000-07:002008-06-22T11:36:00.000-07:00Hmm, I suppose "Kleisli category of T" for some fu...Hmm, I suppose "Kleisli category of T" for some functor T is ambiguous if T is both a monad and a comonad. Then you could say "Kleisli category of T as a monad" and "Kleisli category of T as a comonad", but since they're pretty verbose you'd rather just say "(co)Kleisli category", understanding that "Kleisli" refers to the monad and "coKleisli" to the comonad.Peter Berryhttp://www.blogger.com/profile/08770230331776974807noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-7697808371265044322008-06-22T09:09:00.000-07:002008-06-22T09:09:00.000-07:00Peter:The 'Kleisli category of a comonad' is unamb...Peter:<BR/><BR/>The 'Kleisli category of a comonad' is unambiguous. It is also more verbose than saying 'coKleisli category'. Since one often just says the 'Kleisli construction', this enables the use of 'coKleisli construction' without introducing ambiguity into the root term.<BR/><BR/>That said, one might argue that 'co' is used a little to freely. e.g. Why aren't 'cofree comonads' just free? After all, you have to say 'comonad' in there anyways. On the other hand, you have codensity monads and density comonads, so the co- in the adjective doesn't always follow from the root idea. <BR/><BR/>In the end, I tend to subscribe to the idea that using the shotgun approach of 'co-' everywhere it is applicable enables easier application and facilitates easier communication than requiring the user of the term to know in every case which form is appropriate.Edward Kmetthttp://www.blogger.com/profile/16144424873202502715noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1284429118659839182008-06-21T18:24:00.000-07:002008-06-21T18:24:00.000-07:00What's wrong with the idea of "Kleisli category of...What's wrong with the idea of "Kleisli category of a comonad"? It seems unambiguous to me (even if I don't fully understand comonads). Or is there some difference between "Kleisli" and "coKleisli", e.g. does it make sense to have the coKleisli category of a monad?Peter Berryhttp://www.blogger.com/profile/08770230331776974807noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-86465224050673553702008-06-16T19:48:00.000-07:002008-06-16T19:48:00.000-07:00kim-ee:An implementation of the exponent comonad:h...kim-ee:<BR/><BR/>An implementation of the exponent comonad:<BR/><BR/>http://comonad.com/haskell/category-extras/src/Control/Comonad/Exponent.hs<BR/><BR/>The exponent comonad is to the reader monad what the writer monad is to the product comonad.Edward Kmetthttp://www.blogger.com/profile/16144424873202502715noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-11950039304250740912008-06-16T19:01:00.000-07:002008-06-16T19:01:00.000-07:00Mikael,the dual of the writer monad is takes a com...Mikael,<BR/><BR/>the dual of the writer monad is takes a comonoidal structure. in other words instead of a binary operation <BR/><BR/>join :: a * a -> a, <BR/><BR/>you need a <BR/><BR/>split :: a -> a * a <BR/><BR/>The Iavor's implementation of Augustsson, Rittri, and Synek's Supply comonad (included in category-extras) models this approximately, but uses dirty unsafePerformIO tricks to avoid excessive splitting.<BR/><BR/>http://comonad.com/haskell/category-extras/dist/doc/html/category-extras/Control-Comonad-Supply.html<BR/><BR/>I have intended to get around to adding a SupplyT comonad transformer and a pure Supply comonad, but haven't taken the time.<BR/><BR/>Finally, note that linear implicit parameters in Haskell (plague though they may be on the semantics of Haskell) implement pretty much this very idea and are a useful source of inspiration if you are looking for intuition on the use of this comonad.Edward Kmetthttp://www.blogger.com/profile/16144424873202502715noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-38106102605424048402008-06-16T13:28:00.000-07:002008-06-16T13:28:00.000-07:00Thanks Derek, that paper looks does look interesti...Thanks Derek, that paper looks does look interesting.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-51290850372669232162008-06-16T08:16:00.000-07:002008-06-16T08:16:00.000-07:00Mikael,There is a monoidal comonad, although I'm n...Mikael,<BR/><BR/>There is a monoidal comonad, although I'm not sure you'd want to call it a writer comonad. See <A HREF="http://cs.ioc.ee/~tarmo/monads-more/monads-more-4.pdf" REL="nofollow">Tarmo</A>.<BR/><BR/>The usage is distinctly different, and I don't believe you get another monad/comonad isomorphism. The one above is the only one I know of, a consequence of product being left-adjoint to exponentiation.<BR/><BR/>Perhaps sigfpe might want to blog a nice illustration of the monoidal comonad?Kim-Ee Yeohnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-61714186863530785392008-06-15T12:48:00.000-07:002008-06-15T12:48:00.000-07:00Hmm...if we dualise this we should get the notion ...Hmm...if we dualise this we should get the notion of a coindeterminate, a symbol that sucks the value of subexpressions out of expressions.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-88861101667041415362008-06-15T09:22:00.000-07:002008-06-15T09:22:00.000-07:00Edward, does that difference in categories needed ...Edward, does that difference in categories needed dualize neatly? Is there such a thing as a writer comonad, and do you get similar differences in category properties needed between the writer monad and comonad?Mikael Vejdemo-Johanssonhttp://www.blogger.com/profile/00008302080954798496noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-58622613722284530932008-06-15T07:08:00.000-07:002008-06-15T07:08:00.000-07:00Edward,And of course the 'three way' version of th...Edward,<BR/><BR/>And of course the 'three way' version of the isomorphism I give involving monads requires a CCC as it uses currying. I should write out the full details as it's not in the book. When I have a moment...sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-12453016671922060532008-06-15T03:18:00.000-07:002008-06-15T03:18:00.000-07:00My favorite part about the reader comonad is that ...My favorite part about the reader comonad is that you can define it in weaker categories than you can define the reader monad, for much the same effect. As they noted, the reader comonad works in any Cartesian category, while the reader monad works only in a CCC.Edward Kmetthttp://www.blogger.com/profile/16144424873202502715noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-72176115849349946362008-06-14T18:36:00.000-07:002008-06-14T18:36:00.000-07:00You will probably find this paper and the papers a...You will probably find this paper and the papers also discussed (at least some of which I'm sure you've already read) interesting.<BR/><BR/><A HREF="http://www.kurims.kyoto-u.ac.jp/~hassei/papers/ctcs95.html" REL="nofollow"> Decomposing typed lambda calculus into a couple of categorical programming languages</A>Derek Elkinsnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-36152168313572384492008-06-14T15:46:00.000-07:002008-06-14T15:46:00.000-07:00Anonymous,While I tried to make it clear for categ...Anonymous,<BR/><BR/>While I tried to make it clear for categories, I should have also made it clearer for ordinary polynomials too - you need to have a suitable equivalence relationship on your polynomials before they are in 1-1 correspondence with functions written in terms of elements of R, multiplication and addition.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-43350243859359819852008-06-14T15:39:00.000-07:002008-06-14T15:39:00.000-07:00Nice post. I've also found that haskell can really...Nice post. I've also found that haskell can really help in learning category theory.<BR/><BR/>Btw, what you say about polynomials as functions is incorrect:<BR/><BR/>"So a polynomial in R[x] is the same as a function from R to R that can be written in terms of elements of R, multiplication and addition."<BR/><BR/>This is not true in general, as for example x^p - x == 0 as a function in F_p. It is of course true only for infinite fields.Anonymousnoreply@blogger.com