tag:blogger.com,1999:blog-11295132.post865972317776443412..comments2014-06-25T07:05:59.204-07:00Comments on A Neighborhood of Infinity: Profunctors in HaskellDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-11295132.post-710704377107444582013-04-15T21:39:18.777-07:002013-04-15T21:39:18.777-07:00Profunctors C ↛ D being functors D^op × C → Set is...Profunctors C ↛ D being functors D^op × C → Set is correct, as UpStar turns a functor C → D into a profunctor C ↛ D (and this gives a covariant functor from the category Fun(C,D) of functors to the category Prof(C,D) of profunctors), while DownStar takes a functor D → C to a profunctor C ↛ D (and this gives a contravariant functor). A nice way of looking at profunctors and UpStar is that a functor D^op × C → Set is adjoint to a functor C → Fun(D^op,Set), i.e. a functor C → Presh(D), where by definition Presh(D) is the presheaf category of functors D^op → Set. Then UpStar just takes a functor C → D and composes it with the Yoneda embedding D → Presh(D). (The profunctors in the image of UpStar could be called representable, being precisely the functors C → Presh(D) whose image consists of representable presheaves. Composition of profunctors is easily described in terms of Kleisli composition of such things, since Presh is a monad (the "free cocomplete category" monad).)<br /><br />On that note, the UpStar and DownStar names are backwards. Conventionally in mathematics, a subscript star is used for (the arrow mappings of) covariant functors, while superscript star is used for contravariant functors. But what you call UpStar is <i>co</i>variant (taking functors C → D to profunctors profunctor C ↛ D), while DownStar is contravariant, so the nameing runs contrary to convention and is therefore awfully confusing.Adrian Keethttp://www.blogger.com/profile/00524869184165807497noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-67865091316083462192012-12-29T09:52:28.376-08:002012-12-29T09:52:28.376-08:00> For categories C and D, A profunctor is a fun...> For categories C and D, A profunctor is a functor Dop×C→Set and is written C↛D.<br />You write C↛D and not D↛C there, but that seems confusing since profunctors should generalize hom-functors, yet C↛D is covariant in the first argument and contravariant in the second. The actual profunctor takes argument in the right order, but this is still confusing.<br /><br />So, I'd prefer to update that to read:<br />> For categories C and D, A profunctor is a functor Cop×D→Set and is written C↛D.<br />and update the rest accordingly. I noticed that as a result, UpStar would turn a functor F:C→D into a profunctor F*:D↛C, but I think that flipping shouldn't be a problem, because DownStar would turn a functor F:C→D into a profunctor F_{*}:C↛D (if I'm not mistaken).<br /><br />As a related but distinct change, it would help to rename type variables in:<br />> class Profunctor h where<br />> lmap :: (d' -> d) -> h d c -> h d' c<br />> rmap :: (c -> c') -> h d c -> h d c'<br />to get:<br />> class Profunctor h where<br />> lmap :: (c' -> c) -> h c d -> h c' d<br />> rmap :: (d -> d') -> h c d -> h c d'<br />similarly to what Edward Kmett did in his package:<br />http://hackage.haskell.org/packages/archive/profunctors/3.1.1/doc/html/Data-Profunctor.htmlPaolo G. Giarrussohttp://www.blogger.com/profile/04485097839438234853noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-21373020442888944222011-08-06T21:52:11.397-07:002011-08-06T21:52:11.397-07:00We should have lunch! I'll grab a spot on you...We should have lunch! I'll grab a spot on your calendar.Mike Stayhttp://www.blogger.com/profile/03408641732412584050noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-10393791410745788512011-08-06T06:40:42.029-07:002011-08-06T06:40:42.029-07:00Hi @Mike!
(Via an indirect path) it was your post...Hi @Mike!<br /><br />(Via an indirect path) it was your post that prompted me to write this.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-21045744200981341072011-08-05T16:37:05.202-07:002011-08-05T16:37:05.202-07:00I've updated my blogger profile.I've updated my blogger profile.Mike Stayhttp://www.blogger.com/profile/03408641732412584050noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-23923436081241866672011-08-05T16:35:19.525-07:002011-08-05T16:35:19.525-07:00No, Mike Stay, John Baez' student. I wrote th...No, Mike Stay, John Baez' student. I wrote the Rosetta stone paper with him and I'm almost done with a paper on compact closed bicategories. That's why I was asking about how Haskell dealt with the trace on the Google Haskell list :)<br /><br />Here are some examples from my paper:<br /><br />If you take a monad in Rel, you get a preorder:<br />- A relation H from a set O to itself<br />- An implication xHHy -> xHy, i.e. transitivity<br />- An implication T -> xHx, i.e. reflexivity.<br /><br />If you take a monad in Span(Set), you get a small category:<br />- A span of sets O <-src- M -tgt-> O that maps morphisms to their source & target object<br />- A map of spans involving a function from M x_O M -> M, where M x_O M is the set of composable pairs of morphisms<br />- A map of spans involving a function from O to M picking out the identity.<br /><br />If you take a (symmetric monoidal) monad in Prof, you get an Arrow:<br />- A profunctor A that assigns to any two types the set of abstract programs between them<br />- A natural transformation AA -> A for composition of abstract programs<br />- A natural transformation 1->A for "lifting"mikehttp://www.blogger.com/profile/03408641732412584050noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-35433853719323568832011-08-05T16:18:48.238-07:002011-08-05T16:18:48.238-07:00Hey @mike,
Are you Mike Shulman?Hey @mike,<br /><br />Are you Mike Shulman?sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-57283348851539049512011-08-05T16:15:31.719-07:002011-08-05T16:15:31.719-07:00Oops, I got the objects of Mat(R) wrong. Objects ...Oops, I got the objects of Mat(R) wrong. Objects are natural numbers; morphisms are Ob(R)-valued matrices and 2-morphisms are Mor(R)-valued matrices.mikehttp://www.blogger.com/profile/03408641732412584050noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-9049390934256932262011-08-05T16:00:53.005-07:002011-08-05T16:00:53.005-07:00Hi. Profunctors are one way to categorify linear ...Hi. Profunctors are one way to categorify linear algebra, so you'll get lots of similar constructions. The bicategory Prof is compact closed, where the "opposite" functor is the dual; upstar and downstar are currying and uncurrying.<br /><br />Some other compact closed bicategories are Rel, with sets, relations, and implications; Span(Set), with sets, spans, and maps of spans; Prof and its equivalent 2-category Cocont of presheaf categories, cocontinuous functors, and natural transformations; nCob_2, whose objects are (n-2)-dimensional manifolds, morphisms are (n-1)-dimensional manifolds with boundary, and 2-morphisms are n-dimensional manifolds with corners; and Mat(R) where R is any rig category (it's symmetric monoidal under ⊕, monoidal under ⊗, and ⊗ distributes up to isomorphism over ⊕; Set is the principle example with product & coproduct), whose objects are objects of R, morphisms are Ob(R)-valued matrices, and 2-morphisms are Mor(R)-valued matrices.mikehttp://www.blogger.com/profile/03408641732412584050noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-82064262522497327432011-08-04T04:58:09.193-07:002011-08-04T04:58:09.193-07:00The bifunctor seems more general. I've noticed...The bifunctor seems more general. I've noticed 'lmap' appears to work in reverse, compared to 'first' and it just occured to me as a result of that you wouldn't be able to create an instance of Bifunctor from Profunctor as Bifunctor requires both PFunctor and QFunctor to be parameterized over the same type, p, but I don't think I understand the implications of that.<br />It seems that PFunctor and QFunctor can be easily derived from a Profunctor however.<br /><br /><i><br />newtype a :<- b = W { unW :: b -> a }<br /><br />instance Category (:<-) where<br /> id = W Prelude.id<br /> f . g = W (unW g . unW f)<br /><br />instance Profunctor h => PFunctor h (:<-) (->) where first = lmap . unW<br /><br />instance Profunctor h => QFunctor h (->) (->) where second = rmap<br /></i>Ivan Tomacnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-44851751904825963242011-07-28T10:18:12.245-07:002011-07-28T10:18:12.245-07:00@Ivan Bifunctors are actually different. They are ...@Ivan Bifunctors are actually different. They are functorial in both their arguments, and unlike Profunctors, they don't necessarily map back down to the "base" category, in this case Set.<br /><br />But...Ed has now uploaded a profunctors package.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-18891222570982652242011-07-25T18:00:59.039-07:002011-07-25T18:00:59.039-07:00This naming thing is annoying. I searched Ed's...This naming thing is annoying. I searched Ed's package looking for profunctors and of course failed to find them.<br /><br />I find the name 'distributor' suggestive. You can reproduce some trivial results from functional analysis using them (eg. (->) is the Dirac delta) but I haven't thought of ways to do more ambitious functional analysis type things.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-12997442361657266792011-07-25T17:52:38.341-07:002011-07-25T17:52:38.341-07:00Just thought I'd mention the categories packag...Just thought I'd mention the categories package by Edward Kmett implements this a bit more generally under the name bifunctor.<br />The relation to arrows is also made obvious by calling lmap first and rmap second.Ivan Tomacnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-49237845221429953622011-07-25T15:06:20.266-07:002011-07-25T15:06:20.266-07:00Profunctors is but one of many names for this conc...Profunctors is but one of many names for this concept. Two others are: distributors and C-D-bimodules. Emily Riehl's cute <a href="http://math.uchicago.edu/~eriehl/cat/weighted.pdf" rel="nofollow">paper</a> on weighted (co)limits uses them to good effect. Another nice application of profunctors is the theory of generalized species as described, e.g., <a href="www.cs.le.ac.uk/people/ngambino/Publications/generalised-species.pdf" rel="nofollow">here</a>. (Composition of profunctors can be expressed through a left Kan extension, but I find the definition using coends more transparent. Either follows readily by thinking in analogy to set-theoretic relations though.)Derek Elkinshttp://www.blogger.com/profile/13447153951050085981noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-24332435424837883242011-07-25T13:44:20.834-07:002011-07-25T13:44:20.834-07:00In plain category theory, you can have a (co)end o...In plain category theory, you can have a (co)end of any functor with a type of the form 'C^op x C -> D'. D needn't be symmetric monoidal; just a category. You can also have dinatural transformations between functors of this form. But you cannot have a dinatural transformation for profunctors of the form 'D^op x C -> Set' unless C = D.<br /><br />There apparently is a notion of a (co)end of functors 'C^op x C -> V', with C enriched in V and V symmetric monoidal. But enriched category theory then has (co)ends 'C^op x C -> D' for C and D arbitrary V-enriched categories as well.Dan Doelhttp://www.blogger.com/profile/16761291400347369301noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-39736894026486261162011-07-24T06:42:46.084-07:002011-07-24T06:42:46.084-07:001. I've only ever seen profunctors mapping int...1. I've only ever seen profunctors mapping into Set. I'm guessing that for V-categories you map into V because you want Hom(_,_) (aka. (->)) to be a profunctor.<br /><br />2. Profunctors have different categories but coends restrict to the same category. Coends sort of contract out a repeated index so I'd expect the same category to appear twice.<br /><br />As my discussion is restricted to Hask, I'm always composing profunctors with matching categories, which means they can be composed with coends. In the more general case I think you need Kan extensions. But I haven't thought much about those (for the simple reason you often don't need them when reasoning about Haskell).sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-84137320219248428872011-07-24T01:45:52.624-07:002011-07-24T01:45:52.624-07:00So, I have a two-part question about the generalit...So, I have a two-part question about the generalities between profunctors and coends.<br /><br />First: in the definition of profunctors you give here you restrict to mapping into <b>Set</b> whereas the definition of coend I've seen about allows mapping into any symmetric monoidal category <b>X</b>; I assume this is just you limiting the scope for simplicity of discussion?<br /><br />Second: your definition of profunctors allows the categories <b>C</b> and <b>D</b> to differ, whereas the definitions I've seen for coends has them be the same; is there a reason for this restriction on the definition of coends, or were these other authors just limiting the scope for simplicity?winterkoninkjehttp://winterkoninkje.dreamwidth.org/noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-88543649983775426922011-07-23T18:45:37.064-07:002011-07-23T18:45:37.064-07:00I wasn't objecting to the argument order of Co...I wasn't objecting to the argument order of <i>Compose</i>; my comment was only about the paragraph below <i>exists a. (d -> F a, a -> G c)</i>, in which <i>(f,g)</i> is taken to be of that type. <br /><br />I was just saying that in that case <i>fmap g . f</i> is of type <i>d -> F (G c)</i>, not <i>a -> F (G c)</i> (nothing deep, just a typo I think).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-4414898016223856242011-07-23T16:28:41.833-07:002011-07-23T16:28:41.833-07:00I think my statements are correct, but I made a ba...I think my statements are correct, but I made a bad choice for the definition of Compose. I'm going to flip the definition. Tell me if you think the resulting statements are still incorrect and I'll type up the full working out I have on paper.<br /><br />Thanks for looking closely though!sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-92016687345254610752011-07-23T15:39:19.453-07:002011-07-23T15:39:19.453-07:00I think the
fmap g . f :: a -> F (G C)
should...I think the<br /><br /><i>fmap g . f :: a -> F (G C)</i><br /><br />should be<br /><br /><i>fmap g . f :: d -> F (G c)</i> :)Anonymousnoreply@blogger.com