Interpreters and Natural Transformations

// Natural transformation type alias
type ~>[F[_], G[_]] = FunctionK[F, G]

trait FunctionK[F[_], G[_]] {
  def apply[A](fa: F[A]): G[A]
}

// Execution methods on Free
def foldMap[M[_]](f: FunctionK[S, M])(implicit M: Monad[M]): M[A]
def compile[T[_]](f: FunctionK[S, T]): Free[T, A]
def mapK[T[_]](f: S ~> T): Free[T, A]

// Lambda syntax for natural transformations
def λ[F[_] ~> G[_]](f: F ~> G): F ~> G

// Identity natural transformation
def id[F[_]]: F ~> F

// Composition
def andThen[F[_], G[_], H[_]](f: F ~> G, g: G ~> H): F ~> H
def compose[F[_], G[_], H[_]](g: G ~> H, f: F ~> G): F ~> H

// Define your algebra
sealed trait ConsoleA[A]
case class WriteLine(line: String) extends ConsoleA[Unit]
case class ReadLine() extends ConsoleA[String]

type Console[A] = Free[ConsoleA, A]

def writeLine(line: String): Console[Unit] = Free.liftF(WriteLine(line))
def readLine(): Console[String] = Free.liftF(ReadLine())

// Basic interpreter to Id (for testing)
import cats.Id

val consoleToId: ConsoleA ~> Id = new (ConsoleA ~> Id) {
  def apply[A](fa: ConsoleA[A]): Id[A] = fa match {
    case WriteLine(line) => println(line)
    case ReadLine()      => "test input"
  }
}

// Execute program
val program: Console[String] = for {
  _    <- writeLine("Enter your name:")
  name <- readLine()
  _    <- writeLine(s"Hello, $name!")
} yield name

val result: String = program.foldMap(consoleToId)

import cats.effect.IO

val consoleToIO: ConsoleA ~> IO = new (ConsoleA ~> IO) {
  def apply[A](fa: ConsoleA[A]): IO[A] = fa match {
    case WriteLine(line) => IO(println(line))
    case ReadLine()      => IO(scala.io.StdIn.readLine())
  }
}

// Execute with effects
val ioResult: IO[String] = program.foldMap(consoleToIO)

import cats.data.State

// Key-Value store 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]]
case class Delete(key: String) extends KVStoreA[Unit]

type KVStore[A] = Free[KVStoreA, A]

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

// State interpreter
type KVState = Map[String, Any]
type StateInterpreter[A] = State[KVState, A]

val kvToState: KVStoreA ~> StateInterpreter = new (KVStoreA ~> StateInterpreter) {
  def apply[A](fa: KVStoreA[A]): StateInterpreter[A] = fa match {
    case Put(key, value) => State.modify(_.updated(key, value))
    case Get(key)        => State.inspect(_.get(key).asInstanceOf[Option[A]])
    case Delete(key)     => State.modify(_ - key)
  }
}

// Usage
val kvProgram: KVStore[Option[String]] = for {
  _      <- put("name", "Alice")
  _      <- put("age", 30)
  name   <- get[String]("name")
  _      <- delete("age")
  result <- get[String]("name")
} yield result

val (finalState, result) = kvProgram.foldMap(kvToState).run(Map.empty).value

import cats.data.Writer
import cats.implicits._

// Add logging to any interpreter
def withLogging[F[_], G[_]](
  interpreter: F ~> G,
  logger: F ~> Writer[List[String], ?]
)(implicit G: Monad[G]): F ~> Writer[List[String], G[?]] = {
  
  new (F ~> Writer[List[String], G[?]]) {
    def apply[A](fa: F[A]): Writer[List[String], G[A]] = {
      val logEntry = logger(fa)
      Writer(logEntry.written, interpreter(fa))
    }
  }
}

// Logger for KVStore operations
val kvLogger: KVStoreA ~> Writer[List[String], ?] = new (KVStoreA ~> Writer[List[String], ?]) {
  def apply[A](fa: KVStoreA[A]): Writer[List[String], A] = fa match {
    case Put(key, value) => Writer(List(s"PUT $key = $value"), ())
    case Get(key)        => Writer(List(s"GET $key"), None.asInstanceOf[A]) // Placeholder
    case Delete(key)     => Writer(List(s"DELETE $key"), ())
  }
}

// Note: This is a simplified example - real logging interpreters would be more complex

// Mock interpreter for testing
case class MockConsoleState(inputs: List[String], outputs: List[String])

val mockConsoleInterpreter: ConsoleA ~> State[MockConsoleState, ?] = 
  new (ConsoleA ~> State[MockConsoleState, ?]) {
    def apply[A](fa: ConsoleA[A]): State[MockConsoleState, A] = fa match {
      case WriteLine(line) => 
        State.modify[MockConsoleState](s => s.copy(outputs = s.outputs :+ line))
      case ReadLine() => 
        State { s =>
          s.inputs match {
            case head :: tail => (s.copy(inputs = tail), head.asInstanceOf[A])
            case Nil => (s, "".asInstanceOf[A])
          }
        }
    }
  }

// Test setup
val initialState = MockConsoleState(List("Alice", "Bob"), List())
val (finalState, result) = program.foldMap(mockConsoleInterpreter).run(initialState).value
// finalState.outputs contains all the written lines

// Compose interpreters in sequence
def composeSequential[F[_], G[_], H[_]](
  first: F ~> G,
  second: G ~> H
): F ~> H = new (F ~> H) {
  def apply[A](fa: F[A]): H[A] = second(first(fa))
}

// Example: KVStore -> State -> IO
val kvToIO: KVStoreA ~> IO = composeSequential(kvToState, stateToIO)

def stateToIO[S]: State[S, ?] ~> IO = new (State[S, ?] ~> IO) {
  def apply[A](sa: State[S, A]): IO[A] = {
    // This is simplified - you'd need to manage state properly
    IO(sa.runA(???.asInstanceOf[S]).value)
  }
}

import cats.data.Coproduct

// Define multiple algebras
sealed trait FileA[A]
case class ReadFile(path: String) extends FileA[String]
case class WriteFile(path: String, content: String) extends FileA[Unit]

sealed trait NetworkA[A]
case class HttpGet(url: String) extends NetworkA[String]
case class HttpPost(url: String, body: String) extends NetworkA[String]

// Combine algebras
type AppAlgebra[A] = Coproduct[FileA, NetworkA, A]
type App[A] = Free[AppAlgebra, A]

// Individual interpreters
val fileToIO: FileA ~> IO = new (FileA ~> IO) {
  def apply[A](fa: FileA[A]): IO[A] = fa match {
    case ReadFile(path) => IO(scala.io.Source.fromFile(path).mkString)
    case WriteFile(path, content) => IO {
      val writer = new java.io.PrintWriter(path)
      try writer.write(content) finally writer.close()
    }
  }
}

val networkToIO: NetworkA ~> IO = new (NetworkA ~> IO) {
  def apply[A](fa: NetworkA[A]): IO[A] = fa match {
    case HttpGet(url) => IO(s"GET response from $url")
    case HttpPost(url, body) => IO(s"POST response from $url with $body")
  }
}

// Combine interpreters
val appToIO: AppAlgebra ~> IO = fileToIO or networkToIO

// Helper functions
def readFile(path: String): App[String] = 
  Free.liftF(Coproduct.leftc(ReadFile(path)))

def httpGet(url: String): App[String] = 
  Free.liftF(Coproduct.rightc(HttpGet(url)))

// Combined program
val appProgram: App[String] = for {
  config <- readFile("config.txt")
  result <- httpGet(s"https://api.example.com?config=$config")
} yield result

val finalResult: IO[String] = appProgram.foldMap(appToIO)

sealed trait DatabaseError
case class ConnectionError(message: String) extends DatabaseError
case class QueryError(message: String) extends DatabaseError

sealed trait DatabaseA[A]
case class ExecuteQuery(sql: String) extends DatabaseA[List[String]]
case class ExecuteUpdate(sql: String) extends DatabaseA[Int]

type Database[A] = Free[DatabaseA, A]

val databaseToEither: DatabaseA ~> Either[DatabaseError, ?] = 
  new (DatabaseA ~> Either[DatabaseError, ?]) {
    def apply[A](fa: DatabaseA[A]): Either[DatabaseError, A] = fa match {
      case ExecuteQuery(sql) => 
        if (sql.contains("DROP")) Left(QueryError("DROP not allowed"))
        else Right(List("result1", "result2").asInstanceOf[A])
      case ExecuteUpdate(sql) => 
        if (sql.contains("invalid")) Left(QueryError("Invalid SQL"))
        else Right(1.asInstanceOf[A])
    }
  }

def executeQuery(sql: String): Database[List[String]] = 
  Free.liftF(ExecuteQuery(sql))

val dbProgram: Database[List[String]] = executeQuery("SELECT * FROM users")
val result: Either[DatabaseError, List[String]] = dbProgram.foldMap(databaseToEither)

import cats.MonadError
import cats.effect.IO

val databaseToIO: DatabaseA ~> IO = new (DatabaseA ~> IO) {
  def apply[A](fa: DatabaseA[A]): IO[A] = fa match {
    case ExecuteQuery(sql) => 
      if (sql.contains("DROP")) 
        IO.raiseError(new RuntimeException("DROP not allowed"))
      else 
        IO.pure(List("result1", "result2").asInstanceOf[A])
    case ExecuteUpdate(sql) => 
      if (sql.contains("invalid")) 
        IO.raiseError(new RuntimeException("Invalid SQL"))
      else 
        IO.pure(1.asInstanceOf[A])
  }
}

// Error handling with MonadError
val safeDbProgram = dbProgram.foldMap(databaseToIO).handleErrorWith {
  case error => IO.pure(List(s"Error: ${error.getMessage}"))
}

// Optimize multiple operations into batches
sealed trait OptimizedKVA[A]
case class BatchOps(operations: List[KVStoreA[Any]]) extends OptimizedKVA[List[Any]]

val batchingInterpreter: KVStoreA ~> OptimizedKVA = new (KVStoreA ~> OptimizedKVA) {
  def apply[A](fa: KVStoreA[A]): OptimizedKVA[A] = 
    BatchOps(List(fa)).asInstanceOf[OptimizedKVA[A]]
}

// Then optimize the batched operations
val optimizedToIO: OptimizedKVA ~> IO = new (OptimizedKVA ~> IO) {
  def apply[A](fa: OptimizedKVA[A]): IO[A] = fa match {
    case BatchOps(ops) => 
      // Execute all operations in a single database transaction
      IO(ops.map(executeOperation)).asInstanceOf[IO[A]]
  }
}

def executeOperation(op: KVStoreA[Any]): Any = {
  // Batch execution logic
  ???
}

import org.scalacheck._

// Generate random programs
def genKVProgram: Gen[KVStore[Option[String]]] = for {
  key <- Gen.alphaStr
  value <- Gen.alphaStr
} yield for {
  _      <- put(key, value)
  result <- get[String](key)
} yield result

// Test interpreter equivalence
def interpretersAgree[F[_], A](
  program: Free[F, A],
  interp1: F ~> Id,
  interp2: F ~> Id
): Boolean = {
  program.foldMap(interp1) == program.foldMap(interp2)
}

// Property: mock and real interpreters should agree on pure operations
val interpretEqualityProp = Prop.forAll(genKVProgram) { program =>
  interpretersAgree(program, mockKvInterpreter, realKvInterpreter)
}