How to represent semigroup homomorphism and similars?

Learn
#1

What is the idiomatic way to represent a semigroup/monoid homomorphism?

I know that it is impossible to encode the conditions, but I also think simply using normal functions for homomorphism is against the type-driven practice typical in haskell.

In particular, I need a place to put f (a <> b) = f a <> f b as a verbal constraint. I thought about using typeclasses, but typeclass quite not fits here.

What I want is linear maps, smooth maps and such, but representing monoid homomorphism could be a great start.
So what is the idiomatic way to do this?

#2

How about a type newtype MonoidHomomorphism a b = MonoidHomomophism (a -> b).

EDIT: added newtype

1 Like
#3

You mean newtype? Is it idiomatic haskell to use newtype and explain in comments that it should satisfy certain constraints? Because I heard somewhere that it isn’t good practice to use newtype to enforce constraint…

#4

Seems perfectly reasonable to me.

1 Like
#5

I see, let me go with it. And I thought verbal constraint only applies to typeclasses!!

#6

A common pattern of verbal contracts with newtypes are smart constructors. Usually you define them in an *.Internal module and then only expose safe functions in public modules.

Although, in the case of monoid homomorphisms it is not really possible to make a function that decides whether some function is a monoid homomorphism or not, so this approach cannot be made fully watertight. I could imagine that you could use property-based testing to at least reject functions that are clearly not homomorphisms, but even that sounds difficult.

I would say that a newtype with verbal warnings on unsafe functions is the easiest idiomatic way to do this.

Edit: Here’s an example of my property-based testing idea:

{-# LANGUAGE FlexibleContexts #-}

import Test.LeanCheck

newtype MonoidHomomorphism a b = MkMonoidHomomorhpism
  {runMonoidHomomorphism :: a -> b}

mkMonoidHomomorphism ::
  (Listable a, Show a, Monoid a, Monoid b, Eq b) =>
  (a -> b) ->
  Maybe (MonoidHomomorphism a b)
mkMonoidHomomorphism f
  | f mempty == mempty
    , holds 100 (\x y -> f x <> f y == f (x <> y)) =
    Just (MkMonoidHomomorhpism f)
  | otherwise = Nothing

Obvious downsides are:

  • limited to types that implement the required classes, especially Listable
  • probably poor performance at runtime
  • not actually a proof
2 Likes
#7

Thanks for detailed explanations!
Btw, is it common practice to use long names like MonoidHomomorphism?

#8

I think it is a relatively long name, but I can’t think of a better shorter one.