Add Category instances

[treeowl]

Each type-aligned sequence type forms a category, as explained in the documentation. However, the sequence types are not actually Category instances for some reason.

[suhailshergill]

@atzeus in addition to the above, could we also add instances for basic classes such as Eq, Show etc.?

[treeowl]

@suhailshergill, it's substantially less obvious how to do that appropriately in general.

For Show need the underlying category to offer a very general sort of Show. It would have to look something like this, I believe:

class Show2Strong c where
  show2Strong :: c a b -> String
instance Show2 c => Show (ConsList c a b) where
  ...

This shouldn't really be too difficult to realize, but I doubt many categories will be able to support it, so I don't know that it's worth it. It would also prevent users from writing custom Show instances specialized to particular underlying categories, which could be annoying.

---

The situation is different (in some ways worse, but in some ways better) for Eq. With these particular types, there's absolutely no way to test equality structurally; the existential types may not line up. So there are only two sensible notions of equality:

1. Two type-aligned sequences are equal iff their compositions are equal.
2. Two type-aligned sequences are equal iff their compositions are equal and they have the same length.

It's not terribly clear to me which one is correct.

[treeowl]

I just realized that they are all made Category instances in TASequence.hs, but this is done in a horrifying way that will lead to overlapping instances all over the place. That instance definition should be removed and its contents copied to the various specific types.

[treeowl]

@atzeus, you closed my pull request to fix the Category instances without merging it. Please fix.

[ElvishJerricco]

If every TASequence gives rise to a Category, then Category should be a super class of TASequence, no?

[ElvishJerricco]

Ah, I see. That's not possible because it would require something like RankNTypes on the constraint level.

class (forall c. Category (s c)) => TASequence s where
  ...

Well anyway, this issue should be closed now, right?

[treeowl]

TASequence has the wrong kind for that. However, I would very much like to
have a class

class Category s => MTASequence c s | s -> c where
  (<|) :: c x y -> s y z -> s x z
  (|>) :: s x y -> c y z -> s x z
  ...

This would be more flexible than TASequence in some ways. For example, a
type-aligned sequence specifically for Kleisli categories (as found in some
of the extensible effects work) could have an MTASequence instance, but
not a TASequence one. TASequence is mostly valuable, IMO, for
implementing things like bootstrapped constant-time-append queues. Its
tmap function, I believe, would be better off in another class.

On Tue, Apr 26, 2016 at 2:16 PM, Will Fancher notifications@github.com
wrote:

If every TASequence gives rise to a Category, then Category should be a
super class of TASequence, no?

—
You are receiving this because you authored the thread.
Reply to this email directly or view it on GitHub
#5 (comment)

[ElvishJerricco]

Yea, that would be a much more useful class. But it would end up causing people to use FlexibleContexts and FlexibleInstances a lot, wouldn't it? Not that it would usually be a problem, but they can lead to some violations.