In Scala cats-laws, why is the functor composition law different from canonical definition?

Question

The (covariant) functor definition in cats-laws looks like this:

  def covariantComposition[A, B, C](fa: F[A], f: A => B, g: B => C): IsEq[F[C]] =
    fa.map(f).map(g) <-> fa.map(f.andThen(g))

But if I translate the functor composition rule to Scala, it should be:

rule

  def covariantComposition[A, B, C](fa: F[A], f: A => B, g: B => C): IsEq[F[C]] =
    fa.map(f).andThen(fa.map(g)) <-> fa.map(f.andThen(g))

Why are they different? Which version is correct?

UPDATE 1 I'm aware of a similar implementation in Haskell, but I haven't had a chance to read it. I wonder if the Haskell version is more by the book.

What is this `fa.map(f).andThen` even supposed to mean ? `andThen` is defined on `Functions` for functional composition... `fa.map(f)` gives you `F[B]`... now how is `andThen` even supposed to work with this `Functor` ? Also where is the reference for your given definition of functor composition ? — sarveshseri, Jan 18 '23 at 22:01
@sarveshseri It's just on Wikipedia: https://en.wikipedia.org/wiki/Functor — tribbloid, Jan 18 '23 at 22:26
the output of the functor `F[_]` applied are `F[A] => F[B]` and `F[B] => F[C]` respectively, looks all good to me: https://scastie.scala-lang.org/tribbloid/VyyLFjLwQDiwB8Gs6mYbkA/10 — tribbloid, Jan 18 '23 at 22:36

score 3 · Answer 1 · edited Jan 18 '23 at 23:41

3

I think your confusion comes from the different way functor map property can be represented.

trait Functor[F[_]] {
 
  def map1[A, B](f: A => B): F[A] => F[B]

  def map2[A, B](f: A => B)(fa: F[A]): F[B]

  def map3[A, B](fa: F[A])(f: A => B): F[B]

}

Here... map1 is the haskell aligned definition... and hence the functor law representation used by haskell also works with this one.

So, this haskell

fmap (g . f) = fmap g . fmap f

translates to following Scala

map1( g.compose(f) ) = map1(g).compose( map1(f) )

// or 
map1( f.andThen(g) ) <-> map1(f).andThen(map1(g))

But, the thing is that we have few more ways to represent the same map property as given by map2 and map3. The overall essens is still the same, we just switched the representation.

Now, when we add the full object oriented angle to it... the "object-oriented" Functor becomes something like following.

trait List[+A] {
  def map(f: A => B): List[B]
}

So... for the "object oriented functor" like List, the same law can be represented as following

listA.map(f).map(g) <-> listA.map(f.andThen(g))

And, you are seeing exactly this.

edited Jan 18 '23 at 23:41

Dmytro Mitin

48,194
3
28
66

answered Jan 18 '23 at 22:42

sarveshseri

13,738
28
47

I see, that make sense. Good to know that Haskell is using the more by the book definition – tribbloid Jan 18 '23 at 22:55
I don't know if cats made a good decision tho, there are some type information loss on F[B] comparing to F[A => B], which may cause some problems in summoning type classes precisely – tribbloid Jan 18 '23 at 23:00
@tribbloid Actually, `fmap (g . f) = fmap g . fmap f` is not Haskell. It some meta-Haskell. Equality is not defined for functions in Haskell https://stackoverflow.com/questions/9906628/equality-of-functions-in-haskell – Dmytro Mitin Jan 19 '23 at 00:54
2

@tribbloid I guess you still have some confusion. There doesn't seem to be a type information loss. And type-class laws `... <-> ...` don't make impact on *summoning* type classes in Scala. – Dmytro Mitin Jan 19 '23 at 00:56
In cats this law is enforced by an elaborated property-based test framework, summoning is not required. It may be necessary for a less leaky, more symbolic enforcement, which I don't know yet. In the future I may need to write an autodiff example using this method, just to see which definition is more capable – tribbloid Jan 19 '23 at 01:21

Dmytro Mitin · Accepted Answer · 2023-01-19T01:04:55.933

F(g ∘ f) = F(g) ∘ F(f) is the same as ∀fa, (F(g ∘ f))(fa) = (F(g) ∘ F(f))(fa) (equality of functions is equality of images for all arguments, this is extensionality in HoTT 1 2 3).

The latter is translated as

def covariantComposition[A, B, C](fa: F[A], f: A => B, g: B => C): IsEq[F[C]] =
  fa.map(f).map(g) <-> fa.map(f.andThen(g))

(actually, fa.map(f.andThen(g)) <-> fa.map(f).map(g)).

If you'd like to have "point-free" F(g ∘ f) = F(g) ∘ F(f) you could write _.map(f.andThen(g)) <-> _.map(f).map(g) or _.map(f.andThen(g)) <-> (_.map(f)).andThen(_.map(g)) (this is fmap (g . f) = fmap g . fmap f in Haskell, or more precisely, in some "meta-Haskell").

The 2nd code snippet in your question

def covariantComposition[A, B, C](fa: F[A], f: A => B, g: B => C): IsEq[F[C]] =
  fa.map(f).andThen(fa.map(g)) <-> fa.map(f.andThen(g))

is incorrect. fa.map(f).andThen... doesn't make sense as it was mentioned in comments. You seem to confuse F and F[A].

In category theory, in general categories, f: A -> B can be just arrows, not necessarily functions (e.g. related pairs in a pre-order if a category is this pre-order), so (F(g ∘ f))(fa) can make no sense. But the category of types in Scala (or Haskell) is a category where objects are types and morphisms are functions.

Sorry I just realised that I read it incorrectly, the `.map` used in the law belongs to `Functor.Ops`, it is the inside-out and curried version of `Functor.map`. So in the end this question shouldn't exist :) — tribbloid, Jan 19 '23 at 01:00

In Scala cats-laws, why is the functor composition law different from canonical definition?

2 Answers2