# How to Use `allOfType` to Find All Inequivalent Implementations with Minimal Information Loss in CurryHoward

> Discover how `allOfType` uncovers all distinct implementations of a type in CurryHoward. Filter out suboptimal variants and preserve unique solutions effortlessly.

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

---

**Call `allOfType[T]` to generate every distinct minimal-information-loss implementation of type `T`, filtering out suboptimal variants while preserving all structurally unique solutions.**

The **curryhoward** library for Scala automates proof search to synthesize code from types. When you need to explore every valid implementation of a type without drowning in redundant or low-quality variants, `allOfType` provides the precise API to retrieve all inequivalent solutions that achieve the minimal information-loss score.

## Understanding the `allOfType` API

### How `allOfType` Differs from `ofType` and `anyOfType`

The curryhoward library exposes three distinct entry points for code synthesis, each serving a different exploration need:

| API | Returns | Guarantees |
|-----|---------|------------|
| `ofType[T]` | A **single** implementation (the first minimal-loss term) | May throw if multiple minimal solutions exist, reporting ambiguity. |
| `anyOfType[T]` | **All** proof terms, **including** higher-loss variants | Useful for exhaustive search, but can return a huge set containing redundant or "noisy" implementations. |
| **`allOfType[T]`** | **All inequivalent minimal-loss** implementations | Filters out any term whose `informationLossScore` exceeds the minimum, ensuring a compact yet complete set of optimal solutions. |

Use `allOfType` when you want the complete landscape of "best" implementations without manual combinator gymnastics.

### The Information-Loss Scoring Mechanism

When the theorem prover discovers multiple proof terms for a type, it evaluates each term using `informationLossScore`. This metric, defined in the `TermExpr` implementation, measures structural quality by counting:

- Unused arguments in lambda abstractions
- Amount of eta-reduction required to normalize the term
- Redundant match clauses or unused tuple components

Only terms sharing the **lowest score** survive the filter performed in `TheoremProver.findProofs`. Consequently, `allOfType` never returns two implementations that differ only by trivial syntactic noise.

## How `allOfType` Works Under the Hood

The implementation spans three core source files:

1. **[`src/main/scala/io/chymyst/ch/package.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/package.scala)** (lines 37-48): Defines the `allOfType` macro that generates a Scala AST. This AST runs the theorem prover, collects proofs, and returns a `Seq[T]`.

2. **[`src/main/scala/io/chymyst/ch/Macros.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/Macros.scala)** (lines 404-413): Implements `allOfTypeImplWithValues`, which builds the type expression, incorporates supplied values as named arguments (`arg1`, `arg2`, …), and delegates to `inhabitAllInternal`.

3. **[`src/main/scala/io/chymyst/ch/TheoremProver.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TheoremProver.scala)** (lines 69-77): Contains `findProofs`, which exhaustively searches for proof terms, scores each with the information-loss metric, groups proofs by score, and returns the lowest-scoring group together with the complete proof set.

The macro ultimately wraps each returned term in a lambda-aware class (`Function1Lambda`, `Function2Lambda`, etc.), allowing you to invoke the function normally while retaining access to the underlying proof term.

## Practical Examples of Using `allOfType`

### Basic Usage Without Supplied Values

To find all minimal-loss implementations of a simple function type, import the library and call `allOfType` with the desired type parameter:

```scala
import io.chymyst.ch._

// Find all minimal-loss implementations of (Int, Int) => (Int, Int)
val implementations: Seq[(Int, Int) => (Int, Int)] = allOfType[(Int, Int) => (Int, Int)]

// Inspect the generated lambda terms:
implementations.foreach { impl =>
  println(impl.lambdaTerm.prettyPrint)
}

```

This returns every distinct function that can be built from primitive combinators while preserving the type structure, such as `pair => pair`, `pair => (pair._2, pair._1)`, and other projections. All share the same minimal information-loss score, so none are omitted.

### Providing Existing Values as Building Blocks

When you want synthesized terms to use specific existing functions or values, pass them as additional arguments. The macro treats these as named arguments (`arg1`, `arg2`, …) available within the generated term:

```scala
val inc: Int => Int = _ + 1
val double: Int => Int = _ * 2

// Find all minimal implementations of (Int => Int) => (Int => Int)
val fns: Seq[(Int => Int) => (Int => Int)] = allOfType[(Int => Int) => (Int => Int)](inc, double)

// Examine the lambda term of the first implementation:
println(fns.head.lambdaTerm.prettyPrint)

```

The prover may produce terms such as `g => inc compose g` or `g => double compose g`, using the supplied values as primitive building blocks. Only the minimal-loss variants are returned.

### Inspecting the Underlying `TermExpr`

Each generated value is wrapped in a specialized class that extends the corresponding Scala function trait. To access the raw lambda-calculus representation, use the `lambdaTerm` extension method defined in [`package.scala`](https://github.com/chymyst/curryhoward/blob/main/package.scala):

```scala
val term: TermExpr = implementations.head.lambdaTerm
println(term.prettyPrint)   // Human-readable lambda calculus form

```

The `TermExpr` reveals exactly how the prover constructed the function—showing applications, curried abstractions, and variable bindings—allowing you to verify the synthesized logic or use the term for further metaprogramming.

## When `allOfType` Returns Empty Results

If the type cannot be inhabited given the available values, the theorem prover returns an empty sequence. For example, attempting to synthesize `Int => String` without providing any `String` values or constructors yields no implementations:

```scala
// This returns an empty Seq because no String values are in scope
val empty: Seq[Int => String] = allOfType[Int => String]()

```

This behavior signals a genuine impossibility under the Curry-Howard correspondence—the type is uninhabited with the given assumptions—rather than a library failure.

## Summary

- **`allOfType[T]`** generates every distinct implementation of type `T` that achieves the minimal **information-loss score**, filtering out redundant or suboptimal variants.
- The macro operates by invoking `TheoremProver.findProofs`, which groups proof terms by their `informationLossScore` and returns only the lowest-scoring group.
- Supply existing values as arguments to `allOfType` to incorporate them as named building blocks (`arg1`, `arg2`, etc.) in the synthesized terms.
- Access the underlying `TermExpr` via the `.lambdaTerm` extension to inspect the lambda-calculus representation of each implementation.
- An empty result indicates the type is uninhabited given the available values, following the Curry-Howard correspondence.

## Frequently Asked Questions

### What is the difference between `allOfType` and `anyOfType` in curryhoward?

`anyOfType[T]` returns **every** proof term the theorem prover discovers, including those with high information-loss scores that represent redundant or "noisy" implementations. In contrast, `allOfType[T]` filters this set to return **only** those terms that achieve the minimal information-loss score, giving you all structurally distinct optimal solutions without the clutter of suboptimal variants.

### How does curryhoward calculate information-loss scores?

The library assigns an `informationLossScore` to each `TermExpr` based on structural complexity metrics. The scoring counts unused arguments in lambda abstractions, the amount of eta-reduction required to normalize the term, and redundant pattern-match clauses or unused tuple components. Lower scores indicate implementations that preserve more of the input structure, and `allOfType` exclusively returns terms sharing the lowest score found.

### Can I use `allOfType` with generic or higher-kinded types?

Yes, `allOfType` works with any type the Scala compiler can reify, including generic function types and types involving type constructors, provided the theorem prover can construct a proof term. However, the library operates on the Curry-Howard correspondence, so it can only synthesize total, pure functions. Types requiring side effects, runtime reflection, or external dependencies cannot be inhabited by the prover.

### Why does `allOfType` return an empty sequence for some types?

An empty result indicates that the type is **uninhabited** given the values and functions available in scope. Under the Curry-Howard correspondence, this means there exists no proof term (lambda expression) that can construct a value of the requested type from the provided assumptions. For example, `allOfType[Int => String]()` returns an empty sequence unless you provide a way to produce `String` values from `Int` inputs.