cats-free

import cats.free._
import cats.free.Free
import cats.arrow.FunctionK
import cats.{Functor, Monad, Comonad, Applicative, Eval, InjectK, Defer, Foldable, Traverse}

import cats.free._
import cats.free.Free

// Define your algebra
sealed trait KVStoreA[A]
case class Put[T](key: String, value: T) extends KVStoreA[Unit]
case class Get[T](key: String) extends KVStoreA[Option[T]]

// Create a Free monad
type KVStore[A] = Free[KVStoreA, A]

def put[T](key: String, value: T): KVStore[Unit] = liftF(Put(key, value))
def get[T](key: String): KVStore[Option[T]] = liftF(Get(key))

// Compose operations
val program: KVStore[Option[String]] = for {
  _      <- put("name", "Alice")
  result <- get[String]("name")
} yield result

sealed abstract class Free[S[_], A] extends Product with Serializable

// Constructors
def pure[S[_], A](a: A): Free[S, A]
def liftF[F[_], A](value: F[A]): Free[F, A]
def defer[F[_], A](value: => Free[F, A]): Free[F, A]
def roll[F[_], A](value: F[Free[F, A]]): Free[F, A]

// Monadic operations
def map[B](f: A => B): Free[S, B]  
def flatMap[B](f: A => Free[S, B]): Free[S, B]

// Transformations
def mapK[T[_]](f: S ~> T): Free[T, A]
def compile[T[_]](f: FunctionK[S, T]): Free[T, A]

// Execution
def foldMap[M[_]](f: FunctionK[S, M])(implicit M: Monad[M]): M[A]
def run(implicit S: Comonad[S]): A
def runTailRec(implicit S: Monad[S]): S[A]
def runM[M[_]](f: S[Free[S, A]] => M[Free[S, A]])(implicit S: Functor[S], M: Monad[M]): M[A]

// Evaluation helpers
def step: Free[S, A]
def resume(implicit S: Functor[S]): Either[S[Free[S, A]], A]
def go(f: S[Free[S, A]] => Free[S, A])(implicit S: Functor[S]): A
def fold[B](r: A => B, s: S[Free[S, A]] => B)(implicit S: Functor[S]): B

sealed abstract class FreeT[S[_], M[_], A] extends Product with Serializable

// Constructors
def pure[S[_], M[_], A](value: A)(implicit M: Applicative[M]): FreeT[S, M, A]
def liftF[S[_], M[_], A](value: S[A])(implicit M: Applicative[M]): FreeT[S, M, A]
def liftT[S[_], M[_], A](value: M[A])(implicit M: Functor[M]): FreeT[S, M, A]
def roll[S[_], M[_], A](value: S[FreeT[S, M, A]])(implicit M: Applicative[M]): FreeT[S, M, A]
def defer[S[_], M[_], A](a: M[Either[A, S[FreeT[S, M, A]]]])(implicit M: Applicative[M]): FreeT[S, M, A]

// Monadic operations
def map[B](f: A => B)(implicit M: Applicative[M]): FreeT[S, M, B]
def flatMap[B](f: A => FreeT[S, M, B]): FreeT[S, M, B]

// Transformations
def mapK[N[_]](mn: M ~> N): FreeT[S, N, A]
def hoist[N[_]](mn: FunctionK[M, N]): FreeT[S, N, A]
def compile[T[_]](st: FunctionK[S, T])(implicit M: Functor[M]): FreeT[T, M, A]

// Execution
def foldMap[N[_]](f: FunctionK[S, N])(implicit M: Monad[M], N: Monad[N]): N[A]
def runM(implicit S: Functor[S], M: Monad[M]): M[A]

sealed abstract class FreeApplicative[F[_], A]
def pure[F[_], A](a: A): FreeApplicative[F, A]
def lift[F[_], A](fa: F[A]): FreeApplicative[F, A]
def foldMap[G[_]](f: F ~> G)(implicit G: Applicative[G]): G[A]

final case class Cofree[S[_], A](head: A, tail: Eval[S[Cofree[S, A]]])
def unfold[F[_], A](a: A)(f: A => F[A])(implicit F: Functor[F]): Cofree[F, A]
def extract: A
def coflatMap[B](f: Cofree[S, A] => B)(implicit S: Functor[S]): Cofree[S, B]

// Yoneda lemma - cofree functor
abstract class Yoneda[F[_], A] extends Serializable {
  def apply[B](f: A => B): F[B]
  def run: F[A]
  def map[B](f: A => B): Yoneda[F, B]
  def toCoyoneda: Coyoneda.Aux[F, A, A]
}

// Coyoneda lemma - free functor  
sealed abstract class Coyoneda[F[_], A] extends Serializable {
  type Pivot
  val fi: F[Pivot]
  def k: Pivot => A
  def run(implicit F: Functor[F]): F[A]
  def map[B](f: A => B): Coyoneda[F, B]
  def transform[G[_]](f: FunctionK[F, G]): Coyoneda[G, A]
}

object Coyoneda {
  type Aux[F[_], A, B] = Coyoneda[F, A] { type Pivot = B }
  def lift[F[_], A](fa: F[A]): Coyoneda[F, A]
  def apply[F[_], A, B](fa: F[A])(f: A => B): Aux[F, B, A]
}

object Yoneda {
  def apply[F[_], A](fa: F[A])(implicit F: Functor[F]): Yoneda[F, A]
}

type Trampoline[A] = Free[Function0, A]
def done[A](a: A): Trampoline[A]
def defer[A](a: => Trampoline[A]): Trampoline[A]
def delay[A](a: => A): Trampoline[A]

// Natural transformations
trait FunctionK[F[_], G[_]] extends Serializable {
  def apply[A](fa: F[A]): G[A]
  def compose[E[_]](f: FunctionK[E, F]): FunctionK[E, G]
  def andThen[H[_]](f: FunctionK[G, H]): FunctionK[F, H]
}

// Free monad transformation methods (defined on Free instances)
def mapK[T[_]](f: S ~> T): Free[T, A]
def compile[T[_]](f: FunctionK[S, T]): Free[T, A]

// InjectK for composable algebras
abstract class InjectK[F[_], G[_]] {
  def inj: FunctionK[F, G]
  def prj: FunctionK[G, λ[α => Option[F[α]]]]
  def apply[A](fa: F[A]): G[A]
  def unapply[A](ga: G[A]): Option[F[A]]
}

// Free injection helpers
def liftInject[G[_]]: FreeLiftInjectKPartiallyApplied[G]
def inject[F[_], G[_]]: FreeInjectKPartiallyApplied[F, G]