CODEWITHSUNDEEP
haskellcategoriesfunctor
Ruslan Talpa
Ruslan Talpa

Reputation: 561

Example of defining a functor in haskell between two categories (which are closely related to additive and multiplicative monoids)

I am trying to reconcile the math notion of functor and the haskell notion of it. This article http://brianshourd.com/posts/2012-10-26-tilt-functors-in-haskell.html explains a bit, but maybe someone can provide an example for the following case:

Suppose i define the following categories

Add: where objects are 0,1,2,3,...., morphisms are (0+), (1+), (2+), ... (0+) is the id morph.

Mul: where objects are 0,1,2,3,...., morphisms are (0*), (1*), (2*), ... (1*) is the id morph.

The composition is (.)

How would one define a functor between these two categories in Haskell (if that is possible and if what i described above are categories at all)

Thank you

EDIT: As per @chi suggestion, i am clarifying the question a bit. I am more interested in how you would put/translate into Haskell any functor between these two categories (as opposed to the existence of one, for example map any number to 42 and any morphism to (1*) as @chi sugested)

EDIT 2: Another way to ask this is, how do you reconcile these two statements "the Functor typeclass, which is basically for things that can be mapped over" with "Given categories C and D, a functor F:C→D is a rule that assigns to each object A in C an object F(A) in D. It also assigns to every morphism f:A→B of objects of C a morphism F(f):F(A)→F(B)". If the type constructor [] (lists) is a functor, what are the two categories it connects and how exactly is it mapping objects and morphisms between those two categories

Upvotes: 0

Views: 329

Answers (2)

David Young
David Young

Reputation: 10783

The issue is that Haskell's Functor only represents a certain kind of functor: functors from the category of Haskell types and functions (Hask) to itself. Functor maps types to types (the objects of Hask) and functions to functions (the morphisms of Hask). For instance, the Maybe Functor maps any given type a to the type Maybe a and it uses fmap to map a given function a -> b to a function Maybe a -> Maybe b.

In the category of Hask, the objects are types and the morphisms are functions. Your category has integers as its objects and as a result doesn't fit the pattern of Functor, so the question doesn't quite make sense to ask in this form, at least not with regard to the Functor type class.

Upvotes: 2

tomferon
tomferon

Reputation: 5001

If you look at the definition of the class Category in Haskell, you would see this.

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

See, if the objects in the category are Ints, then you would need to define those functions where a, b and c are Ints. This is fine when objects in the collection are types but not values. So you can't make them an instance of Category.

Also looking at fmap:

 fmap :: (a -> b) -> f a -> f b

You can see it only makes sense with types (thus in the category Hask). If the objects are integers, you would pass morphisms like 4 --> 5 and -> only works with types.

Then (0+) is a morphism from Int to Int. You would need a morphism from, say, 2 to 5.

Maybe it would be something like this:

data IntMorphism = IdMorphism | IntMorphism Int Int

comp :: IntMorphism -> IntMorphism -> IntMorphism
comp IdMorphism m = m
comp m IdMorphism = m
comp  (IntMorphism y' z) (IntMorphism x y)
  | y /= y' = error "can't compose"
  | otherwise = IntMorphism x z

f1 :: Int -> Int
f1 = (+5)

f2 :: IntMorphism -> IntMorphism
f2 IdMorphism = IdMorphism
f2 (IntMorphism x y) = IntMorphism (f1 x) (f1 y)

And the functor laws hold. In particular:

f2 (comp (IntMorphism y z) (IntMorphism x y))
= f2 (IntMorphism x z)
= IntMorphism (f1 x) (f1 z)
= comp (IntMorphism (f1 y) (f1 z)) (IntMorphism (f1 x) (f1 y))
= comp (f2 (IntMorphism y z)) (f2 (IntMorphism x y))

Of course, as it deals with values, it can't use the typeclasses defined in base and it is all done at runtime.

Upvotes: 1

Related Questions