Integrating curryhoward with Cats and Scalaz for Automatic Type Class Derivation

curryhoward can generate Cats and Scalaz type class instances automatically by proving the corresponding type signatures via intuitionistic propositional logic, requiring only thin integration modules to bridge the macro-generated code with library-specific traits.

The chymyst/curryhoward library synthesizes Scala implementations directly from type signatures using an automated theorem prover. Extending this capability to support curryhoward cats scalaz type class derivation would enable developers to obtain lawful Functor, Applicative, and Monad instances for custom data types through a single macro invocation, eliminating boilerplate while preserving compile-time safety.

How curryhoward Generates Code from Types

The Theorem Prover Pipeline

The code generation pipeline centers on src/main/scala/io/chymyst/ch/TheoremProver.scala, which implements an LJT sequent calculus prover for intuitionistic propositional logic (IPL). When a user calls implement, the macro defined in src/main/scala/io/chymyst/ch/Macros.scala extracts the target type U, transforms it into an internal TypeExpr representation (managed in src/main/scala/io/chymyst/ch/TypeExpr.scala), and submits the proof problem to the theorem prover.

Information Loss Scoring

After the prover enumerates all simply-typed lambda calculus (STLC) terms that inhabit the type, TheoremProver.scala scores each candidate by "information loss." This heuristic counts ignored arguments, duplicated variable uses, and constant returns. The macro selects the unique term with the minimum score; if multiple minimal solutions exist, compilation fails with an ambiguity error. This ensures that generated type class instances behave predictably and do not discard data arbitrarily.

Current Type Class Support in curryhoward

Manual Instance Creation

The test suite in src/test/scala/io/chymyst/ch/unit/LawsSpec.scala demonstrates that curryhoward already derives lawful implementations for Functor, Monad, and other algebraic structures. Currently, users must manually wrap the generated code in a trait:

import io.chymyst.ch._

trait FFunctor[F[_]] {
  def f[A, B](f: A => B): F[A] => F[B]
}

implicit val readerFunctor: FFunctor[Reader] = new FFunctor[Reader] {
  def f[A, B] = implement
}

Law Verification

LawsSpec.scala verifies that these generated implementations satisfy functor and monad laws. The library uses the information-loss metric to exclude trivial or diverging implementations, ensuring that map actually applies the function rather than returning a constant.

Integration Architecture for Cats and Scalaz

Macro-Level Derivation

To enable curryhoward cats scalaz type class derivation, new macros such as deriveFunctor[F] and deriveMonad[F] would wrap the existing implement logic. For example, deriveFunctor[Box] would expand to:

implement[(A => B) => Box[A] => Box[B]]

and wrap the resulting term in a cats.Functor[Box] instance.

Optional Module Structure

The core library in src/main/scala/io/chymyst/ch/package.scala must remain dependency-free. Integration modules should reside in src/main/scala/io/chymyst/ch/cats and src/main/scala/io/chymyst/ch/scalaz, declaring Cats or Scalaz as provided dependencies. This allows downstream projects to opt-in without forcing library choices on the ecosystem.

Higher-Kinded Type Handling

For type constructors F[_], the macro must generate polymorphic implementations. The existing LJT prover in src/main/scala/io/chymyst/ch/TheoremProver.scala already handles curried and higher-order types. The primary challenge is scaffolding: deriveMonad[F] would invoke implement separately for pure, flatMap, and map, then compose the results into a cats.Monad[F] instance while reusing the law-checking infrastructure from LawsSpec.scala.

Practical Examples

The following examples illustrate how curryhoward cats scalaz type class derivation would look in practice once the integration modules are implemented.

Deriving a Cats Functor

import cats.Functor
import io.chymyst.ch.cats._   // hypothetical integration module

final case class Wrapper[A](value: A)

// Generates: f => w => Wrapper(f(w.value))
implicit val wrapperFunctor: Functor[Wrapper] = deriveFunctor[Wrapper]

// Usage with Cats syntax
import cats.syntax.functor._
val result = Wrapper(10).map(_ * 2)   // Wrapper(20)

Deriving a Cats Monad

import cats.Monad
import io.chymyst.ch.cats._

case class MyState[S, A](run: S => (A, S))

implicit def myStateMonad[S]: Monad[MyState[S, *]] = 
  deriveMonad[MyState[S, *]]

// Generated implementations:
// pure: a => MyState(s => (a, s))
// flatMap: fsa => f => MyState(s => { val (a, s2) = fsa.run(s); f(a).run(s2) })

Exploring Alternatives with Scalaz

import io.chymyst.ch.scalaz._
import scalaz.Functor

final case class Box[A](value: A)

// allOfType returns all minimal-information-loss implementations
val candidates = allOfType[(A => B) => Box[A] => Box[B]]

candidates.foreach { term =>
  println(term.prettyPrint)   // "f => b => Box(f(b.value))"
}

Summary

• curryhoward synthesizes Scala implementations by proving type signatures in intuitionistic propositional logic using the LJT sequent calculus prover located in src/main/scala/io/chymyst/ch/TheoremProver.scala.
• The library already derives lawful Functor and Monad implementations, as demonstrated in src/test/scala/io/chymyst/ch/unit/LawsSpec.scala, but currently requires manual wrapping in traits.
• curryhoward cats scalaz type class derivation requires thin integration modules that map generated lambda terms to cats.Functor, scalaz.Monad, and similar traits.
• New macros such as deriveFunctor and deriveMonad would invoke the existing implement logic from src/main/scala/io/chymyst/ch/package.scala while handling higher-kinded types and polymorphic method generation.
• The core library should remain dependency-free, with Cats and Scalaz support delivered as optional modules under src/main/scala/io/chymyst/ch/cats and src/main/scala/io/chymyst/ch/scalaz.

Frequently Asked Questions

How does curryhoward generate code from type signatures?

The library uses a macro defined in src/main/scala/io/chymyst/ch/Macros.scala to extract the desired type at compile time. It converts the Scala type into an internal TypeExpr representation and submits it to an LJT theorem prover in src/main/scala/io/chymyst/ch/TheoremProver.scala. The prover searches for a simply-typed lambda calculus term that inhabits the type, scores candidates by information loss, and returns the optimal implementation as Scala source code.

Can curryhoward already derive Cats or Scalaz instances today?

Currently, curryhoward can generate the lambda terms required for Functor, Monad, and other type classes, as shown in src/test/scala/io/chymyst/ch/unit/LawsSpec.scala. However, it does not yet provide the thin wrapper macros needed to automatically produce cats.Functor or scalaz.Functor implicit instances. Users must manually wrap the generated code in the appropriate trait, or wait for the planned integration modules mentioned in the project roadmap.

What is the "information loss" heuristic used by the theorem prover?

The prover in src/main/scala/io/chymyst/ch/TheoremProver.scala enumerates all possible simply-typed lambda calculus terms that satisfy a given type signature. It then scores each term based on "information loss," counting patterns such as ignored arguments, duplicated variable uses, or constant returns. The macro selects the unique term with the minimum score; if multiple terms tie for the lowest score, compilation fails with an ambiguity error, forcing the user to supply a more specific type signature.

How would higher-kinded type derivation work for type classes like Monad?

For higher-kinded types such as F[_], the macro would need to generate polymorphic implementations for methods like flatMap and pure. The existing LJT prover already handles curried and higher-order types, so the primary challenge is scaffolding: the new deriveMonad[F] macro would invoke implement three times—once for pure, once for flatMap, and once for the derived map—and wrap the results in a cats.Monad[F] instance. The macro would also verify that the generated terms compose lawfully, reusing the law-checking infrastructure from src/test/scala/io/chymyst/ch/unit/LawsSpec.scala.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}