Implement combinators module (tuple combinators microlib)

[987Nabil]

Overview

Add a new combinators module providing foundational typeclasses for tuple and sum type operations. These are zero-dependency building blocks used by the schema module and other parts of ZIO Blocks.

Typeclasses

Combiner[L, R]

Bidirectional tuple flattening with combine() and separate().

val c = Combiner[Int, String]
val combined = c.combine(42, "hello")  // (42, "hello")
val (num, str) = c.separate(combined)  // recovers original parts

Zippable[A, B]

One-way tuple flattening with zip() and discard flags. Supports ZIO-style *>, <*, <*> operators.

val z = Zippable[Int, String]
z.zip(42, "hello")  // (42, "hello")

EitherAlternator[L, R]

Either-based alternation for sum types. Works cross-version (Scala 2 + 3).

val alt = EitherAlternator[Int, String]
alt.left(42)    // Left(42)
alt.right("x")  // Right("x")

UnionAlternator[L, R] (Scala 3 only)

Union type alternation (L | R). Rejects same-type combinations since A | A = A.

val alt = UnionAlternator[Int, String]
alt.left(42)    // 42: Int | String
alt.right("x")  // "x": Int | String

StructuralCombiner[A, B] (JVM only, Scala 3 only)

Macro-based structural type merging for combining record-like types.

Module Structure

combinators/
├── jvm/src/main/scala-3/         # StructuralCombiner (JVM-only macro)
├── shared/src/main/scala-2/      # Scala 2 implementations
├── shared/src/main/scala-3/      # Scala 3 implementations  
└── shared/src/test/              # Cross-version tests

Acceptance Criteria

• All typeclasses implemented for Scala 2.13 and Scala 3
• Full test coverage
• Cross-platform support (JVM/JS/Native where applicable)
• Zero external dependencies

[jdegoes]

@987Nabil Let's clean this up while we're at it. Zippable only existed because Combiner was not around at the time; Combiner subsumes Zippable. Also I don't like the names or optionality of the unleft / unright.

Here's a sketch at what I'm looking at:

Tuples, Eithers, and Unions: Algebraic Type Class Guide

Overview

Three families of type classes that provide combining (constructing compound types from simpler ones) and separating (decomposing compound types into simpler ones). Both operations canonicalize their output, meaning input does not need to be in canonical form — canonical structure is a postcondition of every operation, not a precondition on inputs.

Family	Structure	Canonical Form	Example
Tuples	Products	Flat tuple	(A, B, C, D)
Eithers	Tagged sums	Left-nested Either	Either[Either[Either[A, B], C], D]
Unions	Untagged sums	Flat union	A | B | C | D

Canonicalization algorithm (compile-time):

1. Inspect the right branch of the Either.
2. If the right branch is Either[X, Y], reassociate: Either[L, Either[X, Y]] becomes Either[Either[L, X], Y].
3. Repeat until the right branch is atomic.
4. Recurse into the left branch to ensure it's also canonical.

Unions: Flat Canonical Form (Scala 3 only)

Canonical form: A | B | C | D — a flat union with no nested unions (though at the type level, Scala 3 unions are inherently flat and associative, so canonicalization is mostly about the Separator's runtime discrimination order).

Separation convention: The rightmost type member is peeled off, consistent with Tuples and Eithers.

---

Macro Sketches

Scala 2 (Shapeless-style whitebox macros)

// Tuples.Combiner — Scala 2
object Combiner {
  type WithOut[A, B, O] = Combiner[A, B] { type Out = O }
implicit def materialize[A, B]: Combiner[A, B] =

macro CombinerMacros.materialize[A, B]

}
object CombinerMacros {

def materialize[A: c.WeakTypeTag, B: c.WeakTypeTag](

c: whitebox.Context

): c.Tree = {

import c.universe._
// 1. Extract element types from A if it's a TupleN
// 2. Extract element types from B if it's a TupleN
// 3. Concatenate to form flat element list
// 4. Determine output TupleN type
// 5. Generate: new Combiner[A, B] { type Out = ...; def combine(a: A, b: B): Out = ... }

???

}

}
// Tuples.Separator — Scala 2

object Separator {

type WithOut[A, L, R] = Separator[A] { type Left = L; type Right = R }
implicit def materialize[A]: Separator[A] =

macro SeparatorMacros.materialize[A]

}
object SeparatorMacros {

def materialize[A: c.WeakTypeTag](

c: whitebox.Context

): c.Tree = {

import c.universe._
// 1. Flatten A into a list of element types
// 2. Right = last element type
// 3. Left = TupleN of all but last (or bare type if single)
// 4. Generate extraction code that destructures and restructures

???

}

}
// Eithers.Combiner — Scala 2

object EitherCombinerMacros {

def materialize[L: c.WeakTypeTag, R: c.WeakTypeTag](

c: whitebox.Context

): c.Tree = {

import c.universe._
// 1. Inspect R: is it Either[X, Y]?
// 2. If yes, reassociate: Either[L, Either[X, Y]] → Either[Either[L, X], Y]
//    then recurse on the new right branch
// 3. If no, output type is Either[L, R] as-is
// 4. Generate runtime reassociation code (pattern match and re-wrap)

???

}

}
// Eithers.Separator — Scala 2

object EitherSeparatorMacros {

def materialize[A: c.WeakTypeTag](

c: whitebox.Context

): c.Tree = {

import c.universe._
// 1. Inspect A: must be Either[L, R]
// 2. If R is Either[X, Y], reassociate to left-nested form
// 3. After canonicalization, Right = rightmost atomic type
// 4. Left = everything else (may be nested Either)
// 5. Generate pattern matching code that normalizes and separates

???

}

}

Scala 3 (inline + compiletime + Mirror)

// Tuples.Combiner — Scala 3
object Combiner {
  type WithOut[A, B, O] = Combiner[A, B] { type Out = O }
// Compile-time type-level flattening

type Flatten[T] <: Tuple = T match {

case EmptyTuple => EmptyTuple

case h *: t     => h match {

case Tuple => Tuple.Concat[Flatten[h], Flatten[t]]

case _     => h *: Flatten[t]

}

case _          => T *: EmptyTuple

}
type Combined[A, B] = Flatten[A *: B *: EmptyTuple]
inline given [A, B]: Combiner[A, B] =

// Use scala.compiletime.erasedValue, constValueTuple, summonInline

// to generate flattening logic at compile time.

//

// 1. Convert A to tuple representation (identity if already tuple, else wrap)

// 2. Convert B to tuple representation

// 3. Concatenate

// 4. Flatten recursively

//

// Runtime: destructure both inputs, concatenate elements, construct output tuple
???

}
// Tuples.Separator — Scala 3

object Separator {

type WithOut[A, L, R] = Separator[A] { type Left = L; type Right = R }
type Init[T <: Tuple] <: Tuple = T match {

case x *: EmptyTuple => EmptyTuple

case x *: xs         => x *: Init[xs]

}
type Last[T <: Tuple] = T match {

case x *: EmptyTuple => x

case x *: xs         => Last[xs]

}
inline given [A]: Separator[A] =

// 1. Flatten A into canonical flat tuple (reuse Combiner.Flatten)

// 2. Left = Init[Flattened] (all but last)

// 3. Right = Last[Flattened]

// 4. Runtime: flatten, then split
???

}
// Eithers.Combiner — Scala 3

object EitherCombinerMacros {

// Type-level left-nesting

type LeftNest[L, R] = R match {

case Either[x, y] => LeftNest[Either[L, x], y]

case _            => Either[L, R]

}
inline given [L, R]: Eithers.Combiner[L, R] =

// 1. Compute LeftNest[L, R] at compile time

// 2. Generate runtime reassociation via nested pattern matching
???

}
// Eithers.Separator — Scala 3

object EitherSeparatorMacros {

// Type-level extraction of rightmost non-Either type

type RightmostOf[A] = A match {

case Either[l, r] => r match {

case Either[_, _] => RightmostOf[LeftNest[l, r]]

case _            => r

}

}
type AllButRightmost[A] = A match {

case Either[l, r] => r match {

case Either[_, _] => AllButRightmost[LeftNest[l, r]]

case _            => l

}

}
inline given [A]: Eithers.Separator[A] =

// 1. Canonicalize type via LeftNest

// 2. Left = AllButRightmost[A], Right = RightmostOf[A]

// 3. Runtime: pattern match, reassociate if needed, return Either[Left, Right]
???

}
// Unions.Combiner — Scala 3 (unions are Scala 3 only)

object UnionCombinerMacros {

inline given [L, R]: Unions.Combiner[L, R] =

// 1. Out = L | R (Scala 3 automatically flattens union types)

// 2. Runtime: Either[L, R] match { case Left(l) => l; case Right(r) => r }

//    then cast to Out (safe because L <: L | R and R <: L | R)
???

}
// Unions.Separator — Scala 3

object UnionSeparatorMacros {

// Requires scala3-staging or macro annotations to decompose union types.

// Union members are extracted via compiletime.ops.
inline given [A]: Unions.Separator[A] =

// 1. Decompose A into union members at compile time (via TypeRepr in macro)

// 2. Right = last member, Left = union of all others

// 3. Runtime: use TypeTest / isInstanceOf to discriminate

//    if value.isInstanceOf[Right] then Right(value.asInstanceOf[Right])

//    else Left(value.asInstanceOf[Left])

//

// CAVEAT: union discrimination is fragile for erased types.

// Works reliably for distinct concrete types. TypeTest provides

// compile-time warnings when discrimination is unsafe.
???

}

---

Test Suites

Tuples Tests

class TuplesSpec extends AnyFlatSpec with Matchers {
val tuples: Tuples = ??? // production instance
// --- Combiner ---
"Tuples.combine" should "combine two atomic values into a pair" in {

tuples.combine(1, "a") shouldBe (1, "a")

}
it should "append an atomic value to a tuple" in {

tuples.combine((1, "a"), true) shouldBe (1, "a", true)

}
it should "prepend an atomic value to a tuple" in {

tuples.combine(1, ("a", true)) shouldBe (1, "a", true)

}
it should "flatten two tuples" in {

tuples.combine((1, "a"), (true, 3.0)) shouldBe (1, "a", true, 3.0)

}
it should "flatten deeply nested tuples" in {

tuples.combine(((1, "a"), true), (3.0, ('x', "y"))) shouldBe (1, "a", true, 3.0, 'x', "y")

}
// --- Separator ---
"Tuples.separate" should "separate a pair into left and right" in {

tuples.separate((1, "a")) shouldBe (1, "a")

}
it should "peel the rightmost element from a triple" in {

tuples.separate((1, "a", true)) shouldBe ((1, "a"), true)

}
it should "peel the rightmost element from a 4-tuple" in {

tuples.separate((1, "a", true, 3.0)) shouldBe ((1, "a", true), 3.0)

}
it should "canonicalize non-flat input before separating" in {

tuples.separate(((1, "a"), (true, 3.0))) shouldBe ((1, "a", true), 3.0)

}
// --- Round-trip (simple case) ---
"Tuples round-trip" should "recover right element after combine then separate" in {

val combined = tuples.combine((1, "a"), true)

val (left, right) = tuples.separate(combined)

right shouldBe true

left shouldBe (1, "a")

}
// --- Recursive peeling ---
"Tuples recursive peeling" should "fully decompose a tuple" in {

val t = (1, "a", true, 3.0)
val (rest1, d) = tuples.separate(t)
d shouldBe 3.0

val (rest2, c) = tuples.separate(rest1)
c shouldBe true

val (a, b) = tuples.separate(rest2)
a shouldBe 1
b shouldBe "a"

}

}

Eithers Tests

class EithersSpec extends AnyFlatSpec with Matchers {
val eithers: Eithers = ??? // production instance
// --- Combiner ---
"Eithers.combine" should "pass through an already-atomic Either" in {

eithers.combine(Left(1): Either[Int, String]) shouldBe Left(1)

eithers.combine(Right("a"): Either[Int, String]) shouldBe Right("a")

}
it should "reassociate a right-nested Either to left-nested form" in {

// Either[Int, Either[String, Boolean]] → Either[Either[Int, String], Boolean]

val input: Either[Int, Either[String, Boolean]] = Right(Right(true))

val result = eithers.combine(input)

result shouldBe Right(true)
val input2: Either[Int, Either[String, Boolean]] = Right(Left("a"))
val result2 = eithers.combine(input2)
result2 shouldBe Left(Right("a"))

val input3: Either[Int, Either[String, Boolean]] = Left(1)
val result3 = eithers.combine(input3)
result3 shouldBe Left(Left(1))

}
it should "reassociate deeply right-nested Eithers" in {

// Either[A, Either[B, Either[C, D]]] → Either[Either[Either[A, B], C], D]

val input: Either[Int, Either[String, Either[Boolean, Double]]] =

Right(Right(Right(3.0)))

val result = eithers.combine(input)

result shouldBe Right(3.0)

}
// --- Separator ---
"Eithers.separate" should "separate a simple Either" in {

val result = eithers.separate(Left(1): Either[Int, String])

result shouldBe Left(1)
val result2 = eithers.separate(Right("a"): Either[Int, String])
result2 shouldBe Right("a")

}
it should "peel the rightmost alternative from a left-nested Either" in {

// Either[Either[Int, String], Boolean] → Left = Either[Int, String], Right = Boolean

val input: Either[Either[Int, String], Boolean] = Right(true)

val result = eithers.separate(input)

result shouldBe Right(true)
val input2: Either[Either[Int, String], Boolean] = Left(Left(1))
val result2 = eithers.separate(input2)
result2 shouldBe Left(Left(1))

}
it should "canonicalize right-nested input before separating" in {

// Either[Int, Either[String, Boolean]] → canonicalize → separate

val input: Either[Int, Either[String, Boolean]] = Right(Right(true))

val result = eithers.separate(input)

result shouldBe Right(true)

}
// --- Recursive peeling ---
"Eithers recursive peeling" should "fully decompose a nested Either" in {

val input: Either[Either[Either[Int, String], Boolean], Double] = Right(3.0)
val step1 = eithers.separate(input)
step1 shouldBe Right(3.0)

// Simulate Left case traversal
val input2: Either[Either[Either[Int, String], Boolean], Double] =
  Left(Right(true))
val step2a = eithers.separate(input2)
step2a shouldBe Left(Right(true)) // Left is Either[Either[Int, String], Boolean]

// Peel again from the left
val step2b = eithers.separate(Left(Right(true)): Either[Either[Int, String], Boolean])
step2b shouldBe Right(true)

}

}

Unions Tests (Scala 3 only)

class UnionsSpec extends AnyFlatSpec with Matchers {
val unions: Unions = ??? // production instance
// --- Combiner ---
"Unions.combine" should "inject a left value into a union" in {

val result: Int | String = unions.combine(Left(1): Either[Int, String])

result shouldBe 1

}
it should "inject a right value into a union" in {

val result: Int | String = unions.combine(Right("a"): Either[Int, String])

result shouldBe "a"

}
it should "inject into a wider union from compound left" in {

val result: Int | String | Boolean =

unions.combine(Right(true): Either[Int | String, Boolean])

result shouldBe true

}
// --- Separator ---
"Unions.separate" should "discriminate the rightmost member" in {

val v: Int | String | Boolean = true

val result = unions.separate(v)

result shouldBe Right(true)

}
it should "return Left for non-rightmost members" in {

val v: Int | String | Boolean = 42

val result = unions.separate(v)

result shouldBe Left(42) // 42 is in Int | String (the left union)

}
it should "handle string in a three-member union" in {

val v: Int | String | Boolean = "hello"

val result = unions.separate(v)

result shouldBe Left("hello") // "hello" is in Int | String

}
// --- Recursive peeling ---
"Unions recursive peeling" should "fully decompose a union" in {

val v: Int | String | Boolean = "hello"
val step1 = unions.separate(v)
// Right = Boolean, Left = Int | String
step1 shouldBe Left("hello")

step1 match {
  case Left(remaining) =>
    val step2 = unions.separate(remaining)
    // Right = String, Left = Int
    step2 shouldBe Right("hello")
  case Right(_) =>
    fail("Expected Left")
}

}
// --- Round-trip: union → either → union ---
"Unions round-trip" should "survive combine then separate" in {

val original = 42

val combined: Int | String = unions.combine(Left(original): Either[Int, String])

val separated = unions.separate(combined)

separated shouldBe Left(42)

}
// --- Edge case: erased types ---
"Unions.separate" should "handle distinct concrete types reliably" in {

val v: Int | String | Double = 3.14

val result = unions.separate(v)

result shouldBe Right(3.14)

}
// NOTE: Unions with overlapping erased types (e.g., List[Int] | List[String])

// are inherently unsafe and should produce compile-time warnings via TypeTest.

}

Law / Property Tests

class AlgebraicLawsSpec extends AnyFlatSpec with Matchers {
val tuples: Tuples   = ???

val eithers: Eithers = ???

val unions: Unions    = ???
// --- Canonicalization idempotence ---
"Tuples canonicalization" should "be idempotent" in {

// Combining then separating a canonical tuple and re-combining

// should yield the same canonical tuple.

val canonical = (1, "a", true, 3.0)

val (left, right) = tuples.separate(canonical)

val recombined = tuples.combine(left, right)

recombined shouldBe canonical

}
"Eithers canonicalization" should "be idempotent" in {

// Separating a canonical left-nested Either and re-combining

// should yield the same structure.

val canonical: Either[Either[Int, String], Boolean] = Left(Right("a"))

val separated = eithers.separate(canonical)

val recombined = eithers.combine(separated)

recombined shouldBe canonical

}
// --- Separator always produces atomic Right ---
"Tuples.separate right" should "never be a tuple" in {

val (_, right) = tuples.separate((1, "a", true))

right shouldBe a[Boolean] // atomic, not a tuple

}
"Eithers.separate right" should "never be an Either" in {

val result = eithers.separate(

Left(Left(1)): Either[Either[Int, String], Boolean]

)

result match {

case Right(v) => v should not be an[Either[_, ]]

case Left()  => // left is fine

}

}
// --- Combine then separate recovers the right operand ---
"Tuples" should "recover right operand after combine+separate (atomic right)" in {

val combined = tuples.combine((1, "a"), true)

val (_, right) = tuples.separate(combined)

right shouldBe true

}
"Eithers" should "recover right alternative after combine+separate" in {

val combined = eithers.combine(Right(true): Either[Either[Int, String], Boolean])

val separated = eithers.separate(combined)

separated shouldBe Right(true)

}

}

---

Design Decisions and Open Questions

Why sealed trait for the top-level types?

Tuples, Eithers, and Unions are sealed traits to allow controlled extension (e.g., a production implementation provided by a companion object or a test mock), while preventing arbitrary subclassing.

Why Either[L, R] as input to Eithers.Combiner and Unions.Combiner?

Because constructing a sum requires knowing which branch you're injecting. Two separate left/right methods would require the caller to specify both type parameters, but only one can be inferred from the value argument. Accepting Either[L, R] lets both type parameters be inferred from a single argument.

Why does Unions.Separator return Either and not a union?

Because separating is fundamentally about discriminating. A union A | B | C at runtime is just a value — you can't pattern match on union membership without type tests. Separator bridges the untagged world to the tagged world, giving you an Either[A | B, C] that you can match on safely.

Erased type safety for Unions

Union separation relies on runtime type discrimination. This is safe for distinct concrete types (Int | String | Boolean) but unsound for types that erase identically (List[Int] | List[String]). Macro-generated instances should require TypeTest evidence and produce compile-time warnings when discrimination is unsafe.

Non-invertibility of combine/separate

combine followed by separate recovers the right operand only when the right operand is atomic (not itself a compound type of the same family). When the right operand is compound, it gets absorbed into the canonical form and the original grouping is lost. This is by design — canonicalization is more valuable than preserving arbitrary groupings.

[jdegoes]

@987Nabil I have some new and better feedback on this, but it will have to wait for a moment.