FreeT violates the monad laws

[djspiewak]

import cats.{Id, MonadError}
import cats.data.Kleisli
import cats.implicits._
import cats.free.FreeT

type F[A] = Kleisli[FreeT[Id, Either[Int, ?], ?], Unit, A]
val F = MonadError[F, Int]

def run[A](fa: F[A]): Either[Int, A] =
  fa.run(()).runM(ft => Right(ft))

def map1[A, B](fa: F[A])(f: A => B): F[B] =
  fa.map(f)

def map2[A, B](fa: F[A])(f: A => B): F[B] =
  fa.flatMap(a => f(a).pure[F])

val eff1 = F.handleErrorWith(map1(F.fromEither(42.asLeft[String]))(_.asRight[Int]))(_.asLeft[String].pure[F])
val eff2 = F.handleErrorWith(map2(F.fromEither(42.asLeft[String]))(_.asRight[Int]))(_.asLeft[String].pure[F])

run(eff1)   // => Right(Left(42))
run(eff2)   // => Left(42)

The only reason we don't see this on a regular basis is the order in which the traits are composed together within Kleisli. For example:

private[data] trait KleisliMonad[F[_], A]
    extends Monad[Kleisli[F, A, *]]
    with KleisliFlatMap[F, A]
    with KleisliApplicative[F, A] {
  implicit def F: Monad[F]
}

This means we get Applicative's map rather than Monad's, which avoids the bug.

I believe this is being caused by the fact that flatMap is shifted but map is not:

  def map[C](f: B => C)(implicit F: Functor[F]): Kleisli[F, A, C] =
    Kleisli(a => F.map(run(a))(f))

// ...

  def flatMap[C, AA <: A](f: B => Kleisli[F, AA, C])(implicit F: FlatMap[F]): Kleisli[F, AA, C] =
    Kleisli.shift(a => F.flatMap[B, C](run(a))((b: B) => f(b).run(a)))

[djspiewak]

Update: I got Kleisli out of the picture. It's FreeT's fault:

import cats.{Id, MonadError}
import cats.implicits._
import cats.free.FreeT

type F[A] = FreeT[Id, Either[Int, ?], A]
val F = MonadError[F, Int]

def run[A](fa: F[A]): Either[Int, A] =
  fa.runM(ft => Right(ft))

def id[A](fa: F[A]): F[A] = fa.map(a => a)

def map1[A, B](fa: F[A])(f: A => B): F[B] =
  fa.map(f)

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

val eff1 = F.handleErrorWith(map1(F.fromEither(42.asLeft[String]))(_.asRight[Int]))(_.asLeft[String].pure[F])
val eff2 = F.handleErrorWith(map2(F.fromEither(42.asLeft[String]))(_.asRight[Int]))(_.asLeft[String].pure[F])

run(eff1)   // => Right(Left(42))
run(eff2)   // => Left(42)

Update to the update: False alarm. That doesn't quite work. Either way, it's still probably FreeT's fault.

[djspiewak]

Actually minimized:

  test("handle errors in non-head suspensions") {
    type F[A] = FreeT[Id, Option, A]
    val F = MonadError[F, Unit]

    val eff = F.flatMap(F.pure(()))(_ => F.raiseError[String](()))
    F.attempt(eff).runM(Some(_)) should ===(Some(Left(())))
  }

That test fails. The runM produces None.