# Integrating curryhoward with Cats and Scalaz for Automatic Type Class Derivation

> Explore integrating curryhoward with Cats and Scalaz for automatic type class derivation. Generate instances using intuitionistic logic, simplifying your Scala projects.

- Repository: [Chymyst/curryhoward](https://github.com/chymyst/curryhoward)
- Tags: tutorial
- Published: 2026-02-27

---

**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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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:

```scala
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`](https://github.com/chymyst/curryhoward/blob/main/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:

```scala
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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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

```scala
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

```scala
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

```scala
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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/src/test/scala/io/chymyst/ch/unit/LawsSpec.scala).