Incorrect definition of Invariant functor

[cosmin33]

Invariant is now defined as an endofunctor in the category of Equivalence objects; The Equivalence objects are technically isomorphisms, as they adhere to the following laws: to >>> from <-> identity and from >>> to <-> identity

This definition is incorrect, as an invariant functor should be a functor from the category of a pair of functions (A => B, B => A) that don't have to follow the above laws, to the category of scala functions.

For example, I define the following functions:

def to: Int => Long = _.toLong
def from: Long => Int = l => (l % Int.MaxValue.toLong).toInt

These functions don't form an isomorphism because the from function applies a modulo for the long value to obtain an int, and so the second law of isomorphism isn't respected for inputs that are greater than MAXINT.

Let's take another example:

  def to: Int => String = _.toString
  def from: String => Int = s => s.toIntOption.getOrElse(0)

The functions above don't form an isomorphism as in the from function all strings that don't translate to Int return 0 so the second isomorphism law isn't respected

But any of these function pairs should be usable as inputs for an Invariant functor's map function.

So, the Invariant functor shouldn't implement this:

def invmap[A, B](f: A <=> B): F[A] <=> F[B]

but this:

def invmap[A, B](to: A => B, from: B => A): F[A] => F[B]

and the law that an Invariant should abide is:

def invariantComposition[A, B, C](fa: F[A], f1: A => B, f2: B => A, g1: B => C, g2: C => B) =
    fa.invmap(f1, f2).invmap(g1, g2) <-> fa.invmap(f1 >>> g1, g2 >>> f2)

which is more relaxed than the laws of isomorphism

The way the Invariant functor is described now is a particular case of the Invariant functor, a case in which the input function pair forms an isomorphism. But it's a more constrained form than it should be. Maybe it should be defined with another name, like IsoFunctor

[sideeffffect]

@adamgfraser @jdegoes Interesting proposal. What do you guys think of it? Should we just change our current Invariant? Or make this new proposed a parent of our current Invariant? I tried playing with this, but didn't get very far.

[adamgfraser]

There is definitely a version of functor for what you described.

trait Invariant[F[_]] { self =>
  def invmap[A, B](ab: A => B, ba: B => A): F[A] => F[B]
}

However, I'm not sure how useful it is. Invariant is already not the most useful type class as is. The only data types that have Invariant instances that are not also Covariant or Contravariant are some of the type classes like Associative, Commutative, and Identity and Set. You can't do a lot with them but you can do some interesting things like if you have an Associative for one data type and an equivalence to another data type derive an Associative for the other data type.

But those things depend on the functions f and g being value preserving when you go back and forth. In the examples you gave the functions are relatively well behaved in that they are basically a partial isomorphism. But from the type signatures you propose we have no guarantee that is the case and so in general I don't think we could say that there is an Associative[B] given an Associative[A] and some arbitrary functions A => B and B => A.

So I think this may be like Closure where yes some abstraction exists but it has so little structure that it is not particularly useful. I think what could be more useful is the concept of a PartialEquivalence. That is something that I think has enough structure that it could be useful in some cases.

[cosmin33]

It is more useful than you think: Monoids and all algebraic constructs inherited from it (lattices, bands, groups, ...) are derivable with pair of functions (A => B, B => A) that don't have to be an isomorphism. The Associative class (from zio-prelude) being nothing more that a lazy monoid works just the same. Commutative also. Check closely and you'll discover that the isomorphism laws (preserve value as you go back and forth) are not needed to derive these constructs, abiding all their laws, just a pair of opposing functions are enough.

So there's the mistake: To obtain an Associative[B] given an Associative[A] you ask for an A <=> B where a (A => B, B => A) would suffice. More precisely, A <=> B here would be (A => B, B => A) //+ isomorphism laws, so a pair of opposing functions with more restrictions. The same applies for Monoid, CommutativeMonoid, Band, Semilattice, ..., Group, CommutativeGroup, all this algebraic family with 1 or 2 operations based on permutations of associativity, commutativity, idempotence laws. Asking for an isomorphism to functorize these objects when a function pair would suffice only weakens their composability.

There are many constructs however that need an isomorphism to be mapped over. Among them are all the rest of the categorical constructs, as in the categorical world the isomorphism is the most powerful form of equivalence.

[adamgfraser]

I don't think that is right in the absence of additional structure on f and g. For example, let's try to create an Associative[String] given an Associative[Int] and a pair of arbitrary functions:

trait Associative[A] { self =>
  def combine(l: => A, r: => A): A

  def invMap[B](f: A => B, g: B => A): Associative[B] =
    new Associative[B] {
      def combine(l: => B, r: => B): B =
        f(self.combine(g(l), g(r)))
    }
}

object AssociativeSpec extends DefaultRunnableSpec {

  val intAssociative = new Associative[Int] {
    def combine(l: => Int, r: => Int): Int =
      l + r
  }

  def spec: ZSpec[Environment, Failure] =
    suite("AssociativeSpec")(
      testM("invmap") {
        check(Gen.anyString, Gen.anyString, Gen.anyString, Gen.function(Gen.anyString), Gen.function(Gen.anyInt)) {
          (s1, s2, s3, f, g) =>
            val stringAssociative = intAssociative.invMap(f, g)
            val left = stringAssociative.combine(stringAssociative.combine(s1, s2), s3)
            val right = stringAssociative.combine(s1, stringAssociative.combine(s2, s3))
            assert(left)(equalTo(right))
        }
      }
    )
}

The Associative instance we derived doesn't actually describe an associative operation. We need more structure on f and g than just being completely arbitrary functions.

[cosmin33]

The generated functions should still respect the invariant composition law required by the invariant functor:

def invariantComposition[A, B, C](fa: F[A], f1: A => B, f2: B => A, g1: B => C, g2: C => B) =
    fa.invmap(f1, f2).invmap(g1, g2) <-> fa.invmap(f1 >>> g1, g2 >>> f2)

This is the additional structure, so if the above law is respected then associativity should follow. In cats and scalaz they are betting on it. Sadly it's hard to generate said law abiding function pairs to test them.