Functor Monad Type Class Hierarchy

// Functor: things you can map over
trait Functor[F[_]]:
  def map[A, B](fa: F[A])(f: A => B): F[B]

  // Derived
  def as[A, B](fa: F[A], b: B): F[B] = map(fa)(_ => b)
  def void[A](fa: F[A]): F[Unit] = as(fa, ())

// Applicative: independent effects
trait Applicative[F[_]] extends Functor[F]:
  def pure[A](a: A): F[A]
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]

  // Derived
  def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C] =
    ap(map(fa)(a => (b: B) => f(a, b)))(fb)

  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
    map2(fa, fb)((_, _))

  override def map[A, B](fa: F[A])(f: A => B): F[B] =
    ap(pure(f))(fa)

// Monad: sequential effects
trait Monad[F[_]] extends Applicative[F]:
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]

  // Derived
  def flatten[A](ffa: F[F[A]]): F[A] = flatMap(ffa)(identity)

  override def ap[A, B](ff: F[A => B])(fa: F[A]): F[B] =
    flatMap(ff)(f => map(fa)(f))

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

// Instances for Option
given Monad[Option] with
  def pure[A](a: A): Option[A] = Some(a)
  def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] = fa.flatMap(f)

// Instances for List
given Monad[List] with
  def pure[A](a: A): List[A] = List(a)
  def flatMap[A, B](fa: List[A])(f: A => List[B]): List[B] = fa.flatMap(f)

// Instances for Either
given [E]: Monad[[A] =>> Either[E, A]] with
  def pure[A](a: A): Either[E, A] = Right(a)
  def flatMap[A, B](fa: Either[E, A])(f: A => Either[E, B]): Either[E, B] = fa.flatMap(f)

// Generic functions using type classes
def double[F[_]: Functor](fa: F[Int]): F[Int] =
  summon[Functor[F]].map(fa)(_ * 2)

def combine[F[_]: Applicative](fa: F[Int], fb: F[Int]): F[Int] =
  summon[Applicative[F]].map2(fa, fb)(_ + _)

def flatCombine[F[_]: Monad](fa: F[Int])(f: Int => F[Int]): F[Int] =
  summon[Monad[F]].flatMap(fa)(f)

// Monad laws verifier
def verifyMonadLaws[F[_]: Monad, A, B, C](
  a: A,
  fa: F[A],
  f: A => F[B],
  g: B => F[C]
)(using eq: (F[C], F[C]) => Boolean): Boolean =
  val m = summon[Monad[F]]
  // Left identity: pure(a).flatMap(f) == f(a)
  val leftId = eq(m.flatMap(m.pure(a))(f.andThen(m.flatMap(_)(g))),
                  m.flatMap(f(a))(g))
  leftId

@main def run(): Unit =
  // Functor
  println(double(Some(21)))       // Some(42)
  println(double(List(1, 2, 3)))  // List(2, 4, 6)

  // Applicative
  println(combine(Some(10), Some(20)))   // Some(30)
  println(combine(List(1, 2), List(10))) // List(11, 12)

  // Monad
  println(flatCombine(Some(5))(n => Some(n * 2)))  // Some(10)
  println(flatCombine(List(1, 2))(n => List(n, n * 10)))  // List(1,10,2,20)

  // Either
  val either: Either[String, Int] = Right(42)
  println(double(either))  // Right(84)