Twan van Laarhoven wrote:

apfelmus wrote:

class Category c where

...

id :: c a a (.) :: c b c -> c a b -> c a c

...

Unfortunately, the names id and (.) are already taken

I don't see a problem here, if you don't want to use these functions then don't import Control.Category. This is similar to the situation with adding the arrow operators to Data.Tuple.

Yes, except that these here are already in the Prelude. But hey, you can always import Control.Category import Prelude hiding (id,(.))

I am not a category-theorist, but is Category c the right terminology? As I understand it 'c a b' is a morphism between the objects 'a' and 'b' from the category Hask. I don't think there even is a name for the type constructor c itself. When I wrote this exact class for myself a while ago I called it 'Morphism', which makes (some) sense, especially since we also have the 'Arrow' class. But I realize that morphism is not the correct term either.

Yeah, neither terminology is correct, but I'd opt for Category for the following reason: While a and b are objects in the category Hask, they may well be phantom types. For instance, c could implement a small stack based domain specific language and the types merely ensure that all stack operations are ok data C a b = Pop | Swap | Int Int | Float Float | Add data a :- b -- empty data Number -- empty pop :: C (a :- s) s swap :: C (a :- b :- s) (b :- a :- s) int :: Int -> C s (Number :- s) float :: Float -> C s (Number :- s) add :: C (Number :- Number :- s) (Number :- s) In the category Hask, those types Number and a :- b are empty but from the viewpoint of our category of stack operations, there are quite a lot of useful morphisms between them. Thus, in a sense, C can redefine the meaning of objects from Hask, so I think of it as more than a Morphism between objects in Hask. Regards, apfelmus

apfelmus wrote:

Yes, bring 'em in! But _only_ under their standard name :)

class Category c where id :: c a a (.) :: c b c -> c a b -> c a c

class Category cat where id :: cat a a (.) :: cat b c -> cat a b -> cat a c I'm not against this, but it would mean moving Category to the Prelude. As far as bikeshed issues: 1. I don't care either way about the name. "Category" or "Morphism" would both be fine. 2. I made a sort of "minimal bikeshed" patch, with this from Arrow: (>>>) :: comp a b -> comp b c -> comp a c But I actually prefer (<<<) :: comp b c -> comp a b -> comp a c , like (.). I originally called that member 'compose'.

Unfortunately, the names id and (.) are already taken / give headache to those that don't like map :: Functor f => (a -> b) -> f a -> f b .

I prefer the generalised 'map' too. In fact I always use fmap over lists, map is just one more thing to remember so I don't. But that's another proposal... -- Ashley Yakeley Seattle, WA

Conal Elliott wrote:

While we're at it, how about one or more classes in between Category/Compositor and Arrow? One example is DeepArrow (see wiki page [1] and haddock docs [2]). Sample instances: functions and transformers of typed type representations, UIs, code, and pairs of same. I've currently structured DeepArrow as a subclass of Arrow, but most of my instances do not have arr. Any real arrow (including arr) is a DeepArrow (or almost), as the haddock docs mention.

It sounds like DeepArrow should be a superclass of Arrow. Could you give me a good example of a type that is DeepArrow but doesn't have arr?

DeepArrow could benefit from suggestions (perhaps refactoring), and I would appreciate such input. In any case, I imagine there's some rich, useful structure between Category & Arrow, and now would be a great time to explore it before settling on a new class hierarchy.

The only class that comes to mind is a subclass of Category that has arr but not first. But I don't know any instances that aren't Arrows. A full hierarchy might look something like this: class Category cat where id :: cat a a (.) :: cat b c -> cat a b -> cat a c class (Category arr) => PreArrow arr where arr :: (a -> b) -> arr a b class (PreArrow arr) => Arrow arr where arrAp :: arr a (b -> c) -> arr a b -> arr a c (&&&) :: arr a b -> arr a c -> arr a (b,c) class (PreArrow arr) => CoArrow arr where (|||) :: arr a c -> arr b c -> arr (Either a b) c class (Arrow arr,CoArrow arr) => ArrowChoice arr instance (Arrow arr,CoArrow arr) => ArrowChoice arr But I don't know of any useful types that are PreArrow but not Arrow, or CoArrow but not ArrowChoice. -- Ashley Yakeley

Philippa Cowderoy wrote:

The other way round (first but not arr) is arguably more useful - it's the class of embedded first-order compositional languages and with a small amount of work we can even define applicative sugar akin to proc or do. There are all kinds of tasks that can be a big win for!

Could you write out the class? Is it the same as DeepArrow? -- Ashley

Conal Elliott wrote:

While we're at it, how about one or more classes in between Category/Compositor and Arrow?

While looking into functional references I came up with the heirarchy:

class Category (~>) where id :: a ~> a (.) :: (b ~> c) -> (a ~> b) -> (a ~> c)

class Cagegory (~>) => InvArrow (~>) where -- | invArr f g may only be used if g . f = id = f. g invArr :: (a -> b) -> (b -> a) -> (a ~> b)

class InvArrow (~>) => RefArrow (~>) where refArr :: (a -> b) -> (b -> a -> a) -> (a ~> b)

class RefArrow (~>) => Arrow (~>) where arr :: (a -> b) -> (a ~> b)

InvArrow allows invertible functions to be lifted to the arrow type, while RefArrow lifts functional references. I am not too happy about the names, but I like the idea itself. apfelmus wrote:

class Cartesian cat where fst :: cat (a,b) a snd :: cat (a,b) b (&&&) :: cat c a -> cat c b -> cat c (a,b)

with the conditions

fst . (f &&& g) = f snd . (f &&& g) = g

That is not correct, fst . (f &&& g) also has the side effects of g.

get first and second and that would be everything we need for arrows (besides arr ). But IIRC, (&&&) does impose an "order of side effects" on the arguments, so Arrows are more general

For the InvArrow of invertible functions:

data Invertible a b = Invertible { fun :: a -> b, inverse :: b -> a }

The functions (***), first and second are definable, while fan out, (&&&) is not. What I came up with was:

class Category (~>) => CategoryPair (~>) where first :: (a ~> b) -> ((a,d) ~> (b,d)) second :: (a ~> b) -> ((d,a) ~> (d,b)) (***) :: (a ~> b) -> (c ~> d) -> ((a,c) ~> (b,d)) swap :: (a,b) ~> (b,a)

class CategoryPair (~>) => CategoryFanOut (~>) where (&&&) :: (a ~> b) -> (a ~> c) -> (a ~> (b,c))

Exactly the same problem comes up for ArrowChoice and the fan out operator (|||), again the class can be split in two. I am not sure how this should be combined with Conal's deep arrows, perhaps fst and snd could be added to CategoryPair as well. Twan

I like the simplicity of th Cartesian class, including definability of dup, swap, lAssoc, rAssoc, first, and second. I'm missing the significance of

But IIRC, (&&&) does impose an "order of side effects" on the arguments, so Arrows are more general (less restrictive) than cartesian categories.

Is it just that you're wondering with what class to associate the fst/&&& and snd/&&& laws? fst . (f &&& g) = f snd . (f &&& g) = g - Conal On 10/18/07, apfelmus wrote:

Conal Elliott wrote:

...

DeepArrow could benefit from suggestions (perhaps refactoring), and I would appreciate such input. In any case, I imagine there's some rich, useful structure between Category & Arrow, and now would be a great time to explore it before settling on a new class hierarchy.

DeepArrow looks pretty much like a category corresponding to Arrows ("Freyd category" but I don't really know what that is) to me (without a functor arr that embeds the category of Haskell functions).

I mean, Arrows are just computations a ~> b that allow you to keep around temporary variables with first and second . Unfortunately, the Arrow class does not mention all the needed morphisms to do that since the arr function automatically carries most of them over from the category of Haskell functions. I have the feeling that DeepArrow wants to list exactly those necessary morphisms. Perhaps there is something more to DeepArrows, due to the normal function arrows in types, but maybe not since perhaps the only thing they can act on are tuples.

In any case, I'd recommend rethinking DeepArrows, maybe there's some well-known category corresponding to them. For starters, there are cartesian categories, i.e. categories with products:

class Cartesian cat where fst :: cat (a,b) a snd :: cat (a,b) b (&&&) :: cat c a -> cat c b -> cat c (a,b)

with the conditions

fst . (f &&& g) = f snd . (f &&& g) = g

Besides fstA and sndA, this gives the morphisms

dupA = id &&& id -- the diagonal swapA f = snd f &&& fst f lAssocA f = (fst f &&& fst (snd f)) &&& snd (snd f) rAssocA f = fst (fst f) &&& (fst (snd f) &&& snd f)

Interestingly, we already get

first :: Cartesian cat => cat a b -> cat (a,d) (b,d) first f = (f . fst &&& id . snd)

and second and that would be everything we need for arrows (besides arr ). But IIRC, (&&&) does impose an "order of side effects" on the arguments, so Arrows are more general (less restrictive) than cartesian categories. So, it's some (pre?)monoidal category with extra stuff (Freyd?), I don't know :)

Also, I don't know what to do with the Haskell function arrows in the objects (= arguments to ~>) of DeepArrow.

Regards, apfelmus

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

i'm missing a piece of reasoning. how about having &&& as primitive as in your Cartesian proposal, but without the fst/&&& and snd/&&& laws? you could still introduce those laws in a subclass that does not include Arrow. - Conal On 10/22/07, apfelmus wrote:

Conal Elliott wrote:

...

I like the simplicity of th Cartesian class, including definability of dup, swap, lAssoc, rAssoc, first, and second.

I'm missing the significance of

...

But IIRC, (&&&) does impose an "order of side effects" on the arguments, so Arrows are more general (less restrictive) than cartesian categories.

Is it just that you're wondering with what class to associate the fst/&&& and snd/&&& laws?

fst . (f &&& g) = f snd . (f &&& g) = g

Exactly. They often don't hold for Arrows but are taken granted for Cartesian categories. So, using (&&&) as primitive is - despite its elegance - not the right thing to do. (That's also why Arrows have first and second as primitives even when (&&&) makes them superfluous.).

Regards, apfelmus

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

apfelmus wrote:

Conal Elliott wrote:

...

i'm missing a piece of reasoning. how about having &&& as primitive as in your Cartesian proposal, but without the fst/&&& and snd/&&& laws? you could still introduce those laws in a subclass that does not include Arrow.

That would make me feel uncomfortable. At least, I'd drop the name "Cartesian" which intends to allude to "cartesian category".

I can't quite put my finger on it, but I think it's the following: since &&& is somewhat abstract, the best way to characterize it is by laws. I mean, it's the same for monads and return . The fact that return has no side-effects is captured in its entirety by the laws

return x >>= f = f x m >>= return = m

In other words, return is determined uniquely by those two laws. Likewise, the three laws for fst, snd and &&& uniquely determine (up to isomorphism) the notion of "cartesian product" in any category (see also http://en.wikipedia.org/wiki/Product_%28category_theory%29).

If those laws don't hold, I think the most compelling characterization of &&& is indeed in terms of the decomposition

f &&& g = first f . second g

I think that gets the order of side effects wrong. I think you mean: f &&& g = second g . first f (As one can see from the original class default in CategoryFanOut with CategoryPair)

and laws for the new primitives first and second like

first f . first g = first (f . g) second f . second g = second (f . g)

and others.

fst . first f . dup = f snd . second f . dup = f snd . first f . dup = fst . second f . dup ...

It's already tricky to list them all, how to express the fact that first and second pass the other value intact while still performing a potential side effect? And what about a minimal (but still complete) amount of laws?

Well, the type signature of first does not allow much to be done with the snd argument except id. The other tricks are: should dup have no side effects? How to specify?

On 18/10/2007, Cale Gibbard wrote:

Of course, the examples you gave for Compositor are also Functors, but that's not quite the same thing as their Compositor instance.

Oops, disregard that remark, I've been awake too long. ;) - Cale

On 18/10/2007, Twan van Laarhoven wrote:

Cale Gibbard wrote:

...

Hello, just thought I'd finally weigh in on this thread, having given it a little thought.

While there are a few nice examples of instances of Compositor, I think I'd prefer to have (.) be what is currently fmap. Note that it generalises ordinary function composition through the functor ((->) e). Also you get a restricted form of the Arrow case through the inclusion of an instance of Functor for ((~>) e) when (~>) is an Arrow.

The only argument for having (.) = fmap that I can think of is that the types happen to work out. Using (.)/(○) like this is, as far as I know, not standard usage in any way.

We're already not exactly like mathematics in many ways. Having (.) be a symbol for functorial lifting is completely reasonable notationally.

In category theory (.) is composition of morphisms, which is exactly what is proposed for the Category class. You have laws like

...

id . f = f . id = f Of which only the first halve makes sense for fmap.

Function composition forms a monoid, this is still true for composition of morphisms, not for functor application.

Well, functor application is still a kind of monoid action, which is basically what that associativity law says, and of course, you get an analogue to f . id = f whenever your functor has an appropriate analogue to id: the f on the right becomes something akin to pure f, in the applicative or Hughes Arrow sense.

Your argument for seeing (.) as composition on other functors such as lists is that these functors can all be considered a kind of 'functions'. For instance a list is a partial function from the naturals, a pair is a function from unit, etc. I don't think this holds for all functors. What about, say, State or STM?

Well, that part is slightly beside the point, but yeah, State and STM are easy. It's just application of the function to the eventual result of the computation, which is a kind of generalisation of what composition does in the function case.

...

I've tried this out for a while, and it is actually rather nice to use in many cases. Functor application is common enough that having a one-character representation for it is great.

Could you give an example where (.) = fmap actually makes sense for a non-reader functor, and has a clear advantage in readability and understandability over fmap/map/(<$>)?

Sure, it's useful almost anywhere you might make use of any one of those. It's nice because it's visually quiet while still providing some kind of notice that you're lifting the map in question using the functor.

With the Category definition you have for instance functional references:

...

set (head . fst) :: a -> ([a],c) -> ([a],c) set (head . fst) 'a' ("dbc",123) == ("abc",123)

Clearly head and fst here are not the ones in the Prelude!

And bijections:

...

inverse (f . g) == inverse g . inverse f

To summarize: fmap may generalize the type of (.), but that is about all it does. This usage is completely non-standard and, at least to me, unintuitive.

It becomes quite intuitive with a little use. You eventually just regard it as being the same as fmap, but slightly nicer in that the fusion law is made transparent by the notation. It's actually already quite common to define notations in mathematics where application of a function to a structure is functorially lifted. Probably the most common case of this is with the powerset functor. f(S), where S is a subset of the domain of f typically is used to mean the image of S under f: {y : y = f(s), s in S}. Rather than redefining function application polymorphically, this just uses a dot to identify that lifting is taking place. When I first noticed this back several months ago, I was a bit hesitant to propose it. However, functorial application (especially for lists) and function composition being arguably the two most important operations in functional programming, it's rather nice to see that they are really instances of the same thing, and to be able to give them both the nicest possible operator symbol. - Cale

On 19/10/2007, apfelmus wrote:

Cale Gibbard wrote:

...

fmap (f . g) x = fmap f (fmap g x) becomes: (f . g) . x = f . (g . x) fmap id x = x becomes id . x = x

Nice! Can this be done in Category Theory, too? I mean, it would be nice to internalize morphism, functors, natural transformations, ... in one and the same category (like Hask), so there's less fuss. I.e. given a category C , construct an category C\infty that is basically the same as C but also contains the functors, natural transformations etc. of C and has this handy infix (.) operation.

Well, sort of, though they typically don't use quite that notation for it. There is work on generalising to higher-dimensional categories, where, for example, treating Cat as a 2-category, you have 0-cells which are categories, 1-cells, which are functors, and 2-cells, which are natural transformations between parallel functors. Natural transformations support two kinds of composition, called vertical (which is the usual one) and horizontal composition, so typically some separate notation, like an asterisk, is chosen for horizontal composition.

...

I've tried this out for a while, and it is actually rather nice to use in many cases. Functor application is common enough that having a one-character representation for it is great.

I can't remember using fmap/liftM very often, but if I use `liftM`, then often in infix notation, so and infix symbol for fmap is indeed a very good idea.

However, (.) in that role confuses me because I always think that the right argument should be function. In other words, I'm fine with

print . sum . map read . lines . readFile

( with a hypothetical instance Category (a -> IO b) ) while your proposal gives rise to

show . sum . map read . lines . readFile "foo.txt"

which makes me feel ill.

Hmm, it doesn't really bother me so much. There are a number of ways to read that. At the two extremes, you can read it as the composition (show . sum . map read . lines) being functorially applied to (readFile "foo.txt), or as a chain of functor applications with IO as the functor at the other extreme. Of course, these are equal.

In my opinion, function composition and function application should have separate notations. The new (.) blurs these lines too much for my taste (i.e. (.) :: (a -> b) -> Id a -> Id b) and I prefer <$> (or even plain $) for fmap .

In addition, I always longed for categories without an embedding (a -> b) -> c a b , they keep popping up while I program in Haskell and more often than I need infix fmap . Also, I dislike (>>>) or (<<<) and very much prefer (.) for them.

But in the end, we can have both worlds of (.) without name clash! Simply annotate functors with the category they operate on :)

class Category c => Functor c f where (.) :: c a b -> f a -> f b

instance Functor (->) [] where (.) = map

instance Category c => Functor c (c d) where (.) = `o`

Regards, apfelmus

Of course! That's quite a nice idea. Then we can have monads over an arbitrary category on the objects of Hask as well, though I'm not sure of too many examples yet, apart from the obvious one for Arrows. class Functor c m => Monad c m where return :: a -> m a join :: m (m a) -> m a (>>=) :: m a -> (a -> m b) -> m b x >>= f = join (f . x) join x = x >>= id - Cale

Cale Gibbard wrote:

class Functor c m => Monad c m where return :: a -> m a join :: m (m a) -> m a (>>=) :: m a -> (c a (m b)) -> m b x >>= f = join (f . x) join x = x >>= id

We may even want return :: c () a -> m a since there doesn't need to be an embedding from (all of) Hask to c , i.e. the domain and image types may well be phantoms. Regards, apfelmus

Ashley Yakeley wrote:

3. There might be another useful class that's a subclass of Category and a superclass of Arrow, that essentially includes first but not arr. If someone wants to name it and define it, we can put it in the class hierarchy.

My proposal would be the following. The important things are that: 1. It incorporates Conal's deep arrow, 2. as well as everything that is needed for functional references/lenses and bijective/invertible functions. I have chosen to reuse prelude names where possible. class Category cat where id :: cat a a (.) :: cat b c -> cat a b -> cat a c -- | 'cat' can work with pairs class Category cat => CategoryPair cat where fst :: cat (a,b) a snd :: cat (a,b) b swap :: cat (a,b) (b,a) first :: cat a b -> cat (a,c) (b,c) second :: cat a b -> cat (c,a) (c,b) (***) :: cat a b -> cat c d -> cat (a,c) (b,d) snd = fst . swap second f = swap . first f . swap f *** g = second g . first f class CategoryPair cat => CategoryFanOut cat where (&&&) :: cat a b -> cat a c -> cat a (b,c) dup :: cat a (a,a) f &&& g = f *** g . dup -- | 'cat' can work with eithers -- Dual to CategoryPair class Category cat => CategoryChoice cat where inl :: cat a (Either a b) inr :: cat b (Either a b) mirror :: cat (Either a b) (Either b a) left :: cat a b -> cat (Either a c) (Either b c) right :: cat a b -> cat (Either c a) (Either c b) (+++) :: cat a b -> cat c d -> cat (a,c) (b,d) inr = mirror . inl right f = mirror . left f . mirror f +++ g = right g . left f class CategoryChoice cat => CategoryFanIn cat where (|||) :: cat a c -> cat b c -> cat (Either a b) c untag :: cat (Either a a) a f ||| g = untag . f +++ g class Category cat => CategoryZero cat where zeroCat :: cat a b class CategoryZero cat => CategoryPlus cat where (<+>) :: cat a b -> cat a b -> cat a b -- this is what ArrowPlus uses, but perhaps -- (///) is a better choice, because it looks more like the others. class CategoryPair cat => CategoryApply cat where app :: cat (cat a b, a) b class CategoryPair cat => CategoryLoop cat where loop :: cat (a,c) (b,c) -> cat a b -- no idea how useful this is, but it is nice for symmetry class CategoryChoice cat => CategoryCoLoop cat where coloop :: cat (Either a c) (Either b c) -> cat a b -- | Categories that can manipulate functions. -- This is most of 'DeepArrow'. class Category cat => CategoryFun cat where result :: cat b c -> cat (a -> b) (a -> c) curry :: cat ((a, b) -> c) (a -> b -> c) uncurry :: cat (a -> b -> c) ((a, b) -> c) funF :: cat (c -> a, b) (c -> (a, b)) funS :: cat (a, c -> b) (c -> (a, b)) funR :: cat (a -> c -> b) (c -> a -> b) -- instances for t = Either and/or t = (,) -- If h98 compatability is important, it could be split into two classes -- or the functions lrAssocP and lrAssocE (specialized to pair/either) -- could be put into CategoryPair and CategoryChoice respectively. -- Maybe this should be a super class of those two classes: -- class CategoryAssoc cat (,) => CategoryPair cat -- class CategoryAssoc cat Either => CategoryChoice cat -- Then we also have that rAssocP = swap . lAssocP . swap class Category cat => CategoryAssoc cat t where lAssoc :: cat (t a (t b c)) (t (t a b) c) rAssoc :: cat (t (t a b) c) (t a (t b c)) -- | 'cat' contains all invertible functions (bijections) class Category cat => InvArrow cat where arrInv :: (a -> b) -> (b -> a) -> cat a b -- | 'cat' contains all functional references class InvArrow cat => RefArrow cat where arrRef :: (a -> b) -> (b -> a -> a) -> cat a b -- | 'cat' contains all Haskell functions class RefArrow cat => FunArrow cat where arr :: (a -> b) -> cat a b -- For backwards compatability: -- These should be class aliases class (FunArrow cat, CategoryPair cat) => Arrow cat class (Arrow cat, CategoryChoice cat) => ArrowChoice cat class (Arrow cat, CategoryZero cat) => ArrowZero cat class (Arrow cat, CategoryPlus cat) => ArrowPlus cat class (Arrow cat, CategoryApply cat) => ArrowApply cat class (Arrow cat, CategoryLoop cat) => ArrowLoop cat I would further propose that all classes named Category* go into Control.Category, while Arrow* goes into Control.Arrow. The latter can re-export the Control.Category module. And while we are busy messing with the arrows, I think the Kleisli type should change, it can be an instance of most of Category* with just Functor or Applicative instead of requiring the type to be a Monad. Twan

Twan van Laarhoven wrote:

My proposal would be the following. The important things are that: 1. It incorporates Conal's deep arrow, 2. as well as everything that is needed for functional references/lenses and bijective/invertible functions.

I'd opt for more research for that proposal to answer the following essential questions: - Do the classes correspond to already-known categories, i.e. are the class names optimal? - What laws do we expect to hold? - Are the signatures minimal, i.e. does there exist a smaller set of combinators that still achieves the intended effect? Are the signatures complete, i.e. can the intended effect always expressed with the given combinators? - Plenty and useful examples? At least enough examples that fit in the fine grained hierarchy but cannot be fit into a coarser grained one so as to demonstrate the necessity of a fine grained hierarchy. These questions likely have nice answers for many of the classes, but CategoryZero, CategoryPlus, CategoryChoice and in particular CategoryFun may be hard nuts. Also, the proposed subclass chain InvArrow => RefArrow => FunArrow may be cumbersome in practice since it would mean to define three functions instead of just arr when declaring an Arrow. Btw, a better implementation type for functional references / lenses is Lens s a = Lens { focus :: s -> (a, a -> s) } since that allows a more efficient implementation of modify than modify f s = put (f (get s)) s The latter deconstructs s twice whereas the focus primitive works like a zipper. Regards, apfelmus

On Sun, 2007-10-21 at 22:04 +0200, apfelmus wrote:

Twan van Laarhoven wrote:

...

My proposal would be the following. The important things are that: 1. It incorporates Conal's deep arrow, 2. as well as everything that is needed for functional references/lenses and bijective/invertible functions.

I'd opt for more research for that proposal to answer the following essential questions: - Do the classes correspond to already-known categories, i.e. are the class names optimal? - What laws do we expect to hold? - Are the signatures minimal, i.e. does there exist a smaller set of combinators that still achieves the intended effect? Are the signatures complete, i.e. can the intended effect always expressed with the given combinators? - Plenty and useful examples? At least enough examples that fit in the fine grained hierarchy but cannot be fit into a coarser grained one so as to demonstrate the necessity of a fine grained hierarchy.

I tend to agree. Rather than being part of this change, it might be better for someone to work on this as a separate library, and then make a proposal to redefine the Arrow classes once it's well-understood and settled. -- Ashley Yakeley

apfelmus wrote:

Twan van Laarhoven wrote:

...

My proposal would be the following. The important things are that: 1. It incorporates Conal's deep arrow, 2. as well as everything that is needed for functional references/lenses and bijective/invertible functions.

I'd opt for more research for that proposal to answer the following essential questions

Indeed. I have started a project/library at http://code.haskell.org/category/ for this purpose. It contains implementations of functional references and invertible functions as test subjects, and the laws are tested using quickcheck.

- Do the classes correspond to already-known categories, i.e. are the class names optimal? - What laws do we expect to hold?

I have found an example of a law you'd expect to hold, that doesn't. This is: left id == id. For functional references it is not too hard to implement 'left', but it does not satisfy that law, since for the set operation you need two values with the same 'side'. There is no way to get a 'left' value from set (left id) (Left 'a') (Right 'b') = Right 'b' because a might differ from the result type for functions other than id, yet set id (Left 'a') (Right 'b') = Left 'a'

- Are the signatures minimal, i.e. does there exist a smaller set of combinators that still achieves the intended effect? Are the signatures complete, i.e. can the intended effect always expressed with the given combinators?

The big culprit here are the structural combinators: mirror, swap, assoc* and most of CategoryFun (and id). All of these can be written using 'arrInv'. So the questiong becomes: Are there arrows that allow structural manipulation of functions, products and sums, that do not support all bijections? Similairly, injection (inl/inr) and selection (fst/snd) can be written using 'arrRef'. So again: Are there arrows that do not contain the functional references, that do allow inl/inr and fst/snd. A likely candidate for both is Conal's DeepArrow. Another thing I don't like about these functions is that they are specific to (,) and Either. This becomes important once you add syntactic sugar. Case expressions can only be desugared when you have 'arrInv'. Perhaps there can be a superclass of InvArrow with the same type signature, but with the additional requirement that it may only be used for structural isomorphisms.

- Plenty and useful examples? At least enough examples that fit in the fine grained hierarchy but cannot be fit into a coarser grained one so as to demonstrate the necessity of a fine grained hierarchy.

These questions likely have nice answers for many of the classes, but CategoryZero, CategoryPlus

CategoryZero and CategoryPlus just give a monoid structure, exactly the same as MonadZero and MonadPlus. They could be put into a single class like the current MonadPlus. The only reason we need these things are needed is because Haskell doesn't allow universaly quantified contexts f :: CategoryPlus cat => ... f :: (Category cat, forall a b. Monoid (cat a b)) => ...

.. CategoryChoice ..

As mentioned before, CategoryChoice is the dual to CategoryPair. So it is just as reasonable.

and in particular CategoryFun may be hard nuts.

(note: I am brainstorming here) Asside from result, curry, uncurry and funR (aka flip) which can all be expressed with arrInv/arrIso, there are funF and funS which can not. I see no sane way to implement them in anything below ArrowFun. Perhaps these two functions can together form a class class CategoryPair cat => CategoryFunPair cat where funF :: cat (c -> a, b) (c -> (a, b)) funS :: cat (a, c -> b) (c -> (a, b)) funS = result swap . funF . swap And dually class CategoryChoice cat => CategoryFunChoice cat where funL :: cat (Either (c -> a) b) (c -> (Either a b)) funR :: cat (Either a (c -> b)) (c -> (Either a b)) I expect the problem with these classes comes from the fact that they use *two* categories, cat and (->), and a monad. Generalizing to other monads gives for instance funLst :: cat [c -> a] (c -> [a]) Alternatively, it's one category and two monads / applicative functors. Then we get: sequence :: cat (f (g a)) (g (f a)) Now the question becomes: does sequencing in a category cat ever differ from sequencing in (->)? Clearly it can be a subset, but is there anything other than the cases: - f and g commute (f . g = g . f), sequence can be done in IsoArrow - g only sequences through f, we may need a new class for this; otherwise Arrow will do. For some cases RefArrow might be enough. - f and g don't commute, nothing happens. Again I look at Conal for a likely source of examples. Look at Data.Traversable.sequence for this function in (->).

Also, the proposed subclass chain InvArrow => RefArrow => FunArrow may be cumbersome in practice since it would mean to define three functions instead of just arr when declaring an Arrow.

There are examples of all three, and I think it is important to ensure that the instances of the superclasses are available for the subclasses. Otherwise changing a function from, say, FunArrow to RefArrow does not make it more general. Twan

I'm delighted to see these interfaces being explored. Question: why separate fan-out (&&&) from pair? Do you know of type constructors that have fst & snd but not &&&? Similarly for CategoryAssoc. - Conal On 10/21/07, Twan van Laarhoven wrote:

Ashley Yakeley wrote:

...

3. There might be another useful class that's a subclass of Category and a superclass of Arrow, that essentially includes first but not arr. If someone wants to name it and define it, we can put it in the class hierarchy.

My proposal would be the following. The important things are that: 1. It incorporates Conal's deep arrow, 2. as well as everything that is needed for functional references/lenses and bijective/invertible functions. I have chosen to reuse prelude names where possible.

class Category cat where id :: cat a a (.) :: cat b c -> cat a b -> cat a c

-- | 'cat' can work with pairs class Category cat => CategoryPair cat where fst :: cat (a,b) a snd :: cat (a,b) b swap :: cat (a,b) (b,a) first :: cat a b -> cat (a,c) (b,c) second :: cat a b -> cat (c,a) (c,b) (***) :: cat a b -> cat c d -> cat (a,c) (b,d)

snd = fst . swap second f = swap . first f . swap f *** g = second g . first f

class CategoryPair cat => CategoryFanOut cat where (&&&) :: cat a b -> cat a c -> cat a (b,c) dup :: cat a (a,a)

f &&& g = f *** g . dup

-- | 'cat' can work with eithers -- Dual to CategoryPair class Category cat => CategoryChoice cat where inl :: cat a (Either a b) inr :: cat b (Either a b) mirror :: cat (Either a b) (Either b a) left :: cat a b -> cat (Either a c) (Either b c) right :: cat a b -> cat (Either c a) (Either c b) (+++) :: cat a b -> cat c d -> cat (a,c) (b,d)

inr = mirror . inl right f = mirror . left f . mirror f +++ g = right g . left f

class CategoryChoice cat => CategoryFanIn cat where (|||) :: cat a c -> cat b c -> cat (Either a b) c untag :: cat (Either a a) a

f ||| g = untag . f +++ g

class Category cat => CategoryZero cat where zeroCat :: cat a b

class CategoryZero cat => CategoryPlus cat where (<+>) :: cat a b -> cat a b -> cat a b -- this is what ArrowPlus uses, but perhaps -- (///) is a better choice, because it looks more like the others.

class CategoryPair cat => CategoryApply cat where app :: cat (cat a b, a) b

class CategoryPair cat => CategoryLoop cat where loop :: cat (a,c) (b,c) -> cat a b

-- no idea how useful this is, but it is nice for symmetry class CategoryChoice cat => CategoryCoLoop cat where coloop :: cat (Either a c) (Either b c) -> cat a b

-- | Categories that can manipulate functions. -- This is most of 'DeepArrow'. class Category cat => CategoryFun cat where result :: cat b c -> cat (a -> b) (a -> c) curry :: cat ((a, b) -> c) (a -> b -> c) uncurry :: cat (a -> b -> c) ((a, b) -> c) funF :: cat (c -> a, b) (c -> (a, b)) funS :: cat (a, c -> b) (c -> (a, b)) funR :: cat (a -> c -> b) (c -> a -> b)

-- instances for t = Either and/or t = (,) -- If h98 compatability is important, it could be split into two classes -- or the functions lrAssocP and lrAssocE (specialized to pair/either) -- could be put into CategoryPair and CategoryChoice respectively. -- Maybe this should be a super class of those two classes: -- class CategoryAssoc cat (,) => CategoryPair cat -- class CategoryAssoc cat Either => CategoryChoice cat -- Then we also have that rAssocP = swap . lAssocP . swap class Category cat => CategoryAssoc cat t where lAssoc :: cat (t a (t b c)) (t (t a b) c) rAssoc :: cat (t (t a b) c) (t a (t b c))

-- | 'cat' contains all invertible functions (bijections) class Category cat => InvArrow cat where arrInv :: (a -> b) -> (b -> a) -> cat a b

-- | 'cat' contains all functional references class InvArrow cat => RefArrow cat where arrRef :: (a -> b) -> (b -> a -> a) -> cat a b

-- | 'cat' contains all Haskell functions class RefArrow cat => FunArrow cat where arr :: (a -> b) -> cat a b

-- For backwards compatability: -- These should be class aliases class (FunArrow cat, CategoryPair cat) => Arrow cat class (Arrow cat, CategoryChoice cat) => ArrowChoice cat class (Arrow cat, CategoryZero cat) => ArrowZero cat class (Arrow cat, CategoryPlus cat) => ArrowPlus cat class (Arrow cat, CategoryApply cat) => ArrowApply cat class (Arrow cat, CategoryLoop cat) => ArrowLoop cat

I would further propose that all classes named Category* go into Control.Category, while Arrow* goes into Control.Arrow. The latter can re-export the Control.Category module.

And while we are busy messing with the arrows, I think the Kleisli type should change, it can be an instance of most of Category* with just Functor or Applicative instead of requiring the type to be a Monad.

Twan _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Twan van Laarhoven wrote:

My proposal would be the following. The important things are that: 1. It incorporates Conal's deep arrow, 2. as well as everything that is needed for functional references/lenses and bijective/invertible functions. I have chosen to reuse prelude names where possible.

This is a rather finely grained hierarchy, but it's still too coarse to define a category of invertible functions. That category has pairs: it supports first, second and (***), but not fst and snd.

-- | 'cat' can work with pairs class Category cat => CategoryPair cat where fst :: cat (a,b) a snd :: cat (a,b) b swap :: cat (a,b) (b,a) first :: cat a b -> cat (a,c) (b,c) second :: cat a b -> cat (c,a) (c,b) (***) :: cat a b -> cat c d -> cat (a,c) (b,d)

A similar problem exists with inl and inr of CategoryChoice. [snip]

class Category cat => CategoryAssoc cat t where lAssoc :: cat (t a (t b c)) (t (t a b) c) rAssoc :: cat (t (t a b) c) (t a (t b c))

This one is nice. Have you thought about other laws, in particular the distributive laws of sums and products (Either and (,))?

I would further propose that all classes named Category* go into Control.Category, while Arrow* goes into Control.Arrow. The latter can re-export the Control.Category module.

For compatibility reasons, I don't like reusing the Control.Arrow module name. Bertram