How to make a parametrized data type an instance of a Category?

[Bruno Gavranovic]

Hi all,

I'm struggling with one complex problem for quite some time. This is the minimal code that throws an error:

import Control.Category

 

data MyType p a b
  = MyInstance p a b deriving (Show, Eq)

 

myTypeComposition :: MyType q b c -> MyType p a b -> MyType (p, q) a c
myTypeComposition (MyInstance q _ c) (MyInstance p a _) = MyInstance (p, q) a c 

 

instance Category (MyType p) where
  (.) = myTypeComposition

I'm trying to define the composition function for the typeclass Control.Category.

My data type MyType p a b can be thought of as a function form a to b that is parametrized by p.

I want to be able to define many MyTypes and compose them as needed (the actual code has more complex logic, which I removed I so the problem is more obvious). I can compose MyTypes with no problem with the myTypeComposition function I've defined, but I can't use that function as the composition in the Category class.

The problem seems to be in the fact that the result of the composition is of type (p, q) a c. The compiler expects the type p a c, even though that parameter p is not really needed for defining a Category. I do have to put p in when instantiating my type as to make the kinds match, but then compiler expects the result also to be p, which I don't really want.

Any ideas, thoughts? This seems to be a really niche case and I can't find anything useful in google.

--

Bruno Gavranović 

Faculty of electrical engineering and computing | Fakultet elektrotehnike i računarstva

Zagreb, Croatia

mobile phone:  +385 91 755 8798

[Luka Hadžiegrić]

So you want to implement "morphism composition". Such composition must be associative, and from what I can see your `myTypeComposition` breaks that rule. Think about what happens to the first argument (p) when you want to compose 3 MyTypes together. Let's say we have the following types for testing:

data T1
data T2
data T3
data T4
data T5
data T6
data T7

There are two "ways" in which we can compose 3 MyTypes presuming that associativity holds:

test1 :: MyType (T6, (T4, T1)) T7 T3
test1 = ((undefined :: MyType T1 T2 T3) `myTypeComposition` (undefined :: MyType T4 T5 T2)) `myTypeComposition` (undefined :: MyType T6 T7 T5)


test2 :: MyType ((T6, T4), T1) T7 T3
test2 = (undefined :: MyType T1 T2 T3) `myTypeComposition` ((undefined :: MyType T4 T5 T2) `myTypeComposition` (undefined :: MyType T6 T7 T5))

Unfortunately your implementation of "myTypeComposition" is non associative as you can see from the types. Simply by changing the parentheses I get two completely different types.

I'm not sure what you want to achieve exactly, but at the moment your "model" is not a good fit for the Category. Maybe if you describe a bit more what you want to achieve and why you cant just use "myTypeComposition" as is, I could give you more advice.

[Bruno Gavranovic]

Thanks for the feedback!

I somehow overlooked the associativity condition.

Yeah I can just use myTypeComposition, but I was under the impression that I could make it an instance of Category by only satisfying categorical properties for the 2nd and 3rd argument of my datatype.  

I managed to come up with this solution:

import Control.Category

data MyParam p

  = Param p

  | ParamProd (MyParam p) (MyParam p) deriving (Eq, Show)

data MyType p a b

  = MyInstance (MyParam p) a b deriving (Eq, Show)

myComp :: MyType p b c -> MyType p a b -> MyType p a c

myComp (MyInstance q _ c) (MyInstance p a _) = MyInstance (ParamProd p q) a c

instance Category (MyType p) where

  (.) = myComp

at the cost of requiring that composition works only if MyType has the same "p" parameter. All the categorical properties are satisfied now, including associativity. I think this is good enough fo me, for now :)

--
You received this message because you are subscribed to the Google Groups "Haskell-FER" group.
To unsubscribe from this group and stop receiving emails from it, send an email to haskell-fer+unsubscribe@googlegroups.com.
To post to this group, send email to haske...@googlegroups.com.
Visit this group at https://groups.google.com/group/haskell-fer.
For more options, visit https://groups.google.com/d/optout.

[Luka Hadžiegrić]

Clever solution :)

I don't know what you are doing but if you want some "free" exercise you can join us in the making of a new system for PUH course. I think one more person would be just the right amount of people working on the project (there are currently three of us).

There is no pressure, we just want to have something ready before the next PUH iteration so there is still a lot of time.

Here is the link to the issue for discussing features and planning the project. Feel free to join in. I will add you to the organization if you wish contribute (when ever you have time).

https://github.com/FER-PUH/dormouse/issues/1

To unsubscribe from this group and stop receiving emails from it, send an email to haskell-fer...@googlegroups.com.

To post to this group, send email to haske...@googlegroups.com.
Visit this group at https://groups.google.com/group/haskell-fer.
For more options, visit https://groups.google.com/d/optout.