Function composition different behaviour of andThen and compose

I'm currently going through Scala with Cats and enjoying it a lot. In Exercise 4.1.2 (Getting Func-y) we are tasked to implement map using the methods pure and flatMap only.

The code for reference:

import scala.language.higherKinds

trait Monad[F[_]] {
  def pure[A](a: A): F[A]

  def flatMap[A, B](value: F[A])(func: A => F[B]): F[B]

  def map[A, B](value: F[A])(func: A => B): F[B] =
    ???
}

My thinking was as follows:
For the first parameter of flatmap we just pass value.
For the second parameter, we have the function func: A => B and a method pure, which, after eta expansion, has the form pure: A => F[A]. Therefore, we compose pure with func, i.e. we pass pure _ compose func, where pure _ eta expands pure.

map would then look like this:

def map[A, B](value: F[A])(func: A => B): F[B] =
  flatMap(value)(pure _ compose func)

However, this didn't work and produced the following error:

[error] 7:35: type mismatch;
[error]   A => B|scala.Nothing
[error]     flatMap(value)(pure _ compose func)
[error]                                   ^
[info] A => B <: ? => Nothing?
[info] false
[error] 6:30: parameter value func in method map is never used
[error]   def map[A, B](value: F[A])(func: A => B): F[B] =
[error]                              ^
[error] two errors found
[error] (Compile / compileIncremental) Compilation failed

To my surprise, using func andThen pure for the second parameter does compile.

map defined like this compiles:

def map[A, B](value: F[A])(func: A => B): F[B] =
  flatMap(value)(func andThen pure)

I'm surprised because I assumed that for two functions f: A => B and g: B => C, the following would hold:

f andThen g is equivalent to a => g(f(a)) and
g compose f is equivalent to a => g(f(a)),
therefore f andThen g and g compose f are equivalent.

What's the reason that this doesn't hold in general and in this example?

I used scala version 2.13.8 above.

I thought, maybe the problem relates to the eta expansion of the pure method. I found several questions relating to compose and andThen methods as well as eta expansion, but they didn't answer my question.

I found a scala 3 reference entry about Automatic Eta Expansion, so I tried my luck in scala 3.2.1:

trait Monad[F[_]]:
  def pure[A](a: A): F[A]

  def flatMap[A, B](value: F[A])(func: A => F[B]): F[B]

  def map[A, B](value: F[A])(func: A => B): F[B] =
    flatMap(value)(pure compose func)

Notice, how we don't need the underscore after pure anymore (it will be deprecated at some point in the future) because of the automatic eta expansion mentioned in the scala 3 reference article above.

However, this also throws an error:

-- [E007] Type Mismatch Error: --------------------------------------------------------
7 |    flatMap(value)(pure compose func)
  |                   ^^^^^^^^^^^^^^^^^
  |                   Found:    A => F[Any]
  |                   Required: A => F[B]
  |
  |                   where:    F is a type in trait Monad with bounds <: [_] =>> Any

(In the where clause, I don't understand what kind of upper bound [_] =>> Any should be.)

But, again, map using func andThen pure compiles.

Based on the error message, I now believe that the compiler can somehow not infer the correct type because... of the type parameters? I don't know.

Solution

Sometimes eta-expansion is sometimes confusing for the compiler and you have to clarify things yourself.

In Scala 2 I managed to make your code compile with:

def map[A, B](value: F[A])(func: A => B): F[B] =
  flatMap(value)((pure[B](_)).compose(func))

because method _ doesn't always work and method(_) is more in your face (you still have to define [B] to avoid inferring it to something silly like Any or Nothing).

In Scala 3 it works slightly better:

def map[A, B](value: F[A])(func: A => B): F[B] =
  flatMap(value)((pure[B] _).compose(func))

or even

def map[A, B](value: F[A])(func: A => B): F[B] =
  flatMap(value)(pure[B] compose func)

works - you only have to provide [B] explicitly so that it wont attempt to combine Nothing => F[Nothing] with A => B. Currently it cannot be avoided as compiler:

tries to infer types for pure before calling compose on eta-expanded method
since no restriction yet applies, it infers it to Nothing
only then it can infer types on .compose which takes A => B value
however it already inferred that it should be something that is ? => Nothing

so this particular problem comes from compiler not inferring whole expression at once but doing it in chunks.