Newtypes vs constraints : What is Endo really supposed to do?

Learn
#1

In the base documentation, one can read that Endo a is “The monoid of endomorphisms under composition.”

I know what an endomorphism is, but I don’t understand precisely what Endo represents.

My guess is that if the constraint Semigroup a is satisfied, then Endo a is a morphism of semigroups, if Monoid a is satisfied, then it’s a morphism of monoids. The same should apply for any algebraic structures, even if they are not part of base like Group for example.

However, the more I think about it, the more I feel this is wrong. Suppose, for instance, that I’m interested in automorphisms. Then, following the Endo style, I would write something like

newtype Auto x = Auto {appAuto :: x -> x}

But if I do something like this, I will not be able to provide a Group instance for Auto x. So this is bad. Another idea is to write

data Auto x = Auto {appAuto :: Endo x, appInv :: Dual (Endo x)}

Now I will be able to show that Auto x is a group, and it looks like I should be happy. But should I ? I feel like all of this should be defined using classes instead of types.

So here are my questions :

  1. Did I understand correctly what Endo is supposed to do ?
  2. If yes, is it considered a good practice in Haskell to use newtype instead of trying to define a class in such cases ?
#2

When a Haskeller uses any category theory concepts they usually restrict themselves to just the category of sets (and they assume that Haskell somehow relates to that; some claim there is a category Hask of Haskell types and functions).

So, Endo A is just the type of endomorphisms on A in the category of sets, in other words, the functions A -> A.

#3

Thank you for your answer, this makes a lot of sense.

I guess I got confused with the documentation : I do believe it would be useful at this place to distinguish between endomorphisms in the Hask category and endomorphisms of monoids, especially when the module is called Data.Monoid (or Data.Semigroup respectively).

I think this library Data.Monoid.Action makes the same confusion I had (see the documentation of Action (Endo a) a).

#4

The reason that Endo is in Data.Monoid is not because they are endomorphisms in the category of monoids, but because the set of endomorphisms forms a monoid (where the binary operation is function composition and the unit is the identity function).

5 Likes
#5

You should not be happy, Auto x cannot be made a group. Your Dual (Endo x) is not the inverse operation you’d need for a group, it’s a very different kind of dual. Namely

Dual (Endo f) <> Dual (Endo g) == Dual (Endo (g . f))

as opposed to the Dual-less Endo

Endo f <> Endo g == Endo (f . g)
#6

Automorphisms or Homomorphisms in some algebraic category are generally not expressible in Haskell, because the laws the author attached to a type class are not enforced by the compiler. The best that you can do is to say that the set of elements of

data Auto a = Auto {appAuto :: Endo a, appInv :: Endo a}

that satisfy the law appAuto f <> appInv f = Endo id contains the identity and is closed under composition. Thus you have a Haskell type that contains the set of elements that you are interested in, but also has some excess junk that you don’t care about.

For algebraic categories like monoids and groups, you can get halfway to homomorphisms by using a trick: Suppose A is a subcategory of Set and F: Set → Set is the monad of free A algebras on it. Then the Kleisli category of F is isomorphic to the full subcategory of free objects in A.
For example, suppose F is a Haskell monad of linear combinations. Then a Kleisli arrow h :: a -> F b represents a linear map F a -> F b by virtue of (=<<). The monad laws ensure that (=<<) h preserves the structure that is implicit in F.
For details see this literate haskell file.

1 Like
#7

Very interesting, thanks a lot !