# How CurryHoward Handles Tuples and Functions with Arity Greater Than 2

> Discover how CurryHoward elegantly manages tuples and functions with arity greater than 2 by encoding them as named conjunctions and nested curried terms.

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

---

**CurryHoward represents both tuples and multi-argument functions in a curried normal form, encoding tuples as named conjunctions (`NamedConjunctE`) and functions with arity greater than 2 as nested `CurriedE` terms that store a list of bound variables and a body expression.**

The `chymyst/curryhoward` library implements the Curry-Howard correspondence for Scala, automatically generating proof terms for type signatures. Understanding how curryhoward handles tuples and functions with arity greater than 2 is essential for debugging generated code and optimizing proof search heuristics. The library normalizes all arities through currying and named conjunctions, maintaining a uniform term language regardless of argument count.

## Tuple Representation via Named Conjunctions

### NamedConjunctT and NamedConjunctE Encoding

In [`src/main/scala/io/chymyst/ch/TypeExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TypeExpr.scala), tuple types are represented as `NamedConjunctT`, a case-class-like type constructor. When constructing a tuple term, `TypeExpr.apply` creates a `NamedConjunctE` that stores the component values.

```scala
// TypeExpr.apply creates a tuple term from a NamedConjunctT
// → NamedConjunctE(args, nct)               // src/main/scala/io/chymyst/ch/TypeExpr.scala#L15-L22

```

The concrete term that stores the tuple values is a `NamedConjunctE` (see the case class definition in [`src/main/scala/io/chymyst/ch/TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TermExpr.scala) at lines 714-718).

### Accessing Components with ProjectE

Individual tuple elements are accessed via `ProjectE` defined in [`src/main/scala/io/chymyst/ch/TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TermExpr.scala). The projection extracts the i-th component from the wrapped list inside `NamedConjunctE`.

```scala
// ProjectE(index, term) extracts the i-th part of a tuple
// → term.t match { case NamedConjunctT(_, _, _, wrapped) ⇒ wrapped(index) }  // src/main/scala/io/chymyst/ch/TermExpr.scala#L44-L52

```

### Tuple Usage Statistics for Proof Optimization

The implementation tracks `unusedTupleParts` and `usedTuplePartsSeq` to calculate `informationLossScore`, guiding the LJT proof search heuristics. This addresses the limitation that `Ordering` is undefined on tuples with more than 9 elements (see the comment "Need to split the tuple into parts because Ordering[] is undefined on tuples > 9" in [`src/main/scala/io/chymyst/ch/TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TermExpr.scala) at lines 48-50).

## Curried Representation for Functions with Arity Greater Than 2

### The CurriedE Case Class

Multi-argument functions normalize to `CurriedE(heads: List[VarE], body: TermExpr)` in [`src/main/scala/io/chymyst/ch/TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TermExpr.scala). The `heads` list contains bound variables for each argument, and the type is constructed by folding left-to-right over reversed heads.

```scala
final case class CurriedE(heads: List[VarE], body: TermExpr) extends TermExpr   // src/main/scala/io/chymyst/ch/TermExpr.scala#L682-L687

```

### Applying Arguments with applyCurried

The helper method `applyCurried` in [`TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/TermExpr.scala) handles application of curried functions to multiple arguments sequentially, using `AppE` nodes for each application step.

```scala
// Apply this curried function to a number of arguments at once.
def applyCurried(curriedFunction: TermExpr, args: Seq[TermExpr]): TermExpr =
  args.foldLeft[TermExpr](curriedFunction) { case (prev, arg) ⇒ AppE(prev, arg) }   // src/main/scala/io/chymyst/ch/TermExpr.scala#L99-L102

```

`AppE` creates a regular application node; repeated folding yields the fully applied term.

### Integration with Proof Search

The curried representation integrates deeply with the proof engine. `Sequent.substituteInto` uses `applyCurried` to instantiate premises (see [`src/main/scala/io/chymyst/ch/Sequent.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/Sequent.scala) at lines 16-17), while [`src/main/scala/io/chymyst/ch/LJT.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/LJT.scala) constructs curried terms during proof building at lines 121, 155, 241, 376, and 378.

## Interaction Between Tuples and Multi-Argument Functions

When a function expects a tuple as a single argument, the system uses `NamedConjunctE` directly. For multiple distinct arguments, `CurriedE` represents the function, and `ProjectE` can extract tuple components to feed into curried functions. This unified approach allows the prover to treat argument groups consistently regardless of whether they are packaged as tuples or separate parameters.

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

// 1️⃣ Tuple (named conjunction) -------------------------------------------------
case class Pair[A, B](a: A, b: B)               // a case class becomes a NamedConjunctT
val pairType: TypeExpr = NamedConjunctT("Pair",
  List(TP("A"), TP("B")), List("a", "b"), List(TP("A"), TP("B")))

val tup: TermExpr = pairType.apply(VarE("x", TP("A")), VarE("y", TP("B"))) // → NamedConjunctE(...)
println(tup.prettyPrint)   // Pair(x, y)

// Project the first component
val fst = tup.apply(0)      // same as ProjectE(0, tup)
println(fst.prettyPrint)   // x

// 2️⃣ Multi‑argument function (arity > 2) ---------------------------------------
val tA = TP("A"); val tB = TP("B"); val tC = TP("C")
val fBody = VarE("x", tA) ->: VarE("y", tB) ->: VarE("z", tC) ->: VarE("x", tA) // λx.λy.λz. x
val curriedF = CurriedE(List(VarE("x", tA), VarE("y", tB), VarE("z", tC)), fBody)

// Apply three arguments at once
val applied = TermExpr.applyCurried(curriedF,
  Seq(VarE("p", tA), VarE("q", tB), VarE("r", tC)))
println(applied.prettyPrint) // (p q r) → p

// 3️⃣ Function taking a tuple as a single argument -----------------------------
val gBody = VarE("t", pairType) ->: VarE("t", pairType).apply(0) // λt. fst(t)
val curriedG = CurriedE(List(VarE("t", pairType)), gBody)

val result = TermExpr.applyCurried(curriedG, Seq(tup))
println(result.prettyPrint)   // fst(Pair(x, y))  → x

```

## Summary

- CurryHoward normalizes all tuples to `NamedConjunctE` terms and `NamedConjunctT` types, with component access via `ProjectE`.
- Functions with arity greater than 2 are represented as `CurriedE` containing a list of bound variables (`heads`) and a body expression.
- The `applyCurried` helper method chains `AppE` applications to fully instantiate curried functions.
- Proof search integration in [`Sequent.scala`](https://github.com/chymyst/curryhoward/blob/main/Sequent.scala) and [`LJT.scala`](https://github.com/chymyst/curryhoward/blob/main/LJT.scala) relies on these representations to build valid proof terms.
- Tuple usage statistics (`unusedTupleParts`, `informationLossScore`) guide heuristics in the LJT prover, addressing Scala's `Ordering` limitations on large tuples.

## Frequently Asked Questions

### How does curryhoward represent a Scala function with three arguments?

It converts the function to a `CurriedE` term containing three bound variables in the `heads` list. The type is constructed by nesting function arrows right-associatively, effectively representing `A => B => C => D` internally while preserving the association between variables and their types.

### What is the difference between NamedConjunctE and CurriedE in curryhoward?

`NamedConjunctE` represents product types (tuples) where all components exist simultaneously as a single value, while `CurriedE` represents functions where arguments are applied sequentially. A tuple is a single value containing multiple accessible parts via `ProjectE`, whereas a curried function is a chain of single-argument functions built via `applyCurried`.

### How does the library handle tuple projection for large arities?

The `ProjectE` class extracts components by index from the `wrapped` list inside `NamedConjunctE`. For tuples with more than nine elements, the implementation avoids Scala's built-in `Ordering` limitation by tracking usage statistics (`unusedTupleParts`) to calculate `informationLossScore`, which guides proof search heuristics without requiring lexicographic ordering comparisons.

### Where does the proof search engine construct curried terms?

The LJT prover in [`src/main/scala/io/chymyst/ch/LJT.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/LJT.scala) constructs `CurriedE` terms at lines 121, 155, 241, 376, and 378 during proof building. Additionally, `Sequent.substituteInto` in [`src/main/scala/io/chymyst/ch/Sequent.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/Sequent.scala) uses `applyCurried` to instantiate premises with found proof terms, ensuring consistent handling of multi-argument functions throughout the proof search process.