SIP-58 - Named Tuples

Language

By: Martin Odersky

History

Date Version
Jan 13th 2024 Initial Draft

Summary

We propose to add new form of tuples where the elements are named. Named tuples can be types, terms, or patterns. Syntax examples:

type Person = (name: String, age: Int)
val Bob: Person = (name = "Bob", age = 33)

Bob match
  case (name = n, age = 22) => ...

We also propose to revive SIP 43 to support patterns with named fields. Named pattern fields for case classes are analogous to named patterns for tuple elements. User-defined named pattern matching is supported since named tuples can be results of extractor methods.

Motivation

  1. Named tuples are a convenient lightweight way to return multiple results from a function. But the absence of names obscures their meaning, and makes decomposition with _1, _2 ugly and hard to read. The existing alternative is to define a class instead. This does name fields, but is more heavy-weight, both in terms of notation and generated bytecode. Named tuples give the same convenience of definition as regular tuples at far better readability.

  2. Named tuples are an almost ideal substrate on which to implement relational algebra and other database oriented operations. They are a good representation of database rows and allow the definition of generic operations such as projections and joins since they can draw on Scala 3’s existing generic machinery for tuples based on match types.

  3. Named tuples make named pattern matching trivial to implement. The discussion on SIP 43 showed that without them it’s unclear how to implement named pattern matching at all.

Proposed solution

The elements of a tuple can now be named. Example:

type Person = (name: String, age: Int)
val Bob: Person = (name = "Bob", age = 33)

Bob match
  case (name, age) =>
    println(s"$name is $age years old")

val persons: List[Person] = ...
val minors = persons.filter: p =>
  p.age < 18

Named bindings in tuples are similar to function parameters and arguments. We use name: Type for element types and name = value for element values. It is illegal to mix named and unnamed elements in a tuple, or to use the same same name for two different elements.

Fields of named tuples can be selected by their name, as in the line p.age < 18 above.

Example:

// This is an @main method
@main def foo(x: Int): Unit =
  println(x)

Conformance and Convertibility

The order of names in a named tuple matters. For instance, the type Person above and the type (age: Int, name: String) would be different, incompatible types.

Values of named tuple types can also be be defined using regular tuples. For instance:

val Laura: Person = ("Laura", 25)

def register(person: Person) = ...
register(person = ("Silvain", 16))
register(("Silvain", 16))

This follows since a regular tuple (T_1, ..., T_n) is treated as a subtype of a named tuple (N_1 = T_1, ..., N_n = T_n) with the same element types.

In the other direction, one can convert a named tuple to an unnamed tuple with the toTuple method. Example:

val x: (String, Int) = Bob.toTuple // ok

toTuple is defined as an extension method in the NamedTuple object. It returns the given tuple unchanged and simply “forgets” the names.

A .toTuple selection is inserted implicitly by the compiler if it encounters a named tuple but the expected type is a regular tuple. So the following works as well:

val x: (String, Int) = Bob  // works, expanded to Bob.toTuple

The difference between subtyping in one direction and automatic .toTuple conversions in the other is relatively minor. The main difference is that .toTuple conversions don’t work inside type constructors. So the following is OK:

  val names = List("Laura", "Silvain")
  val ages = List(25, 16)
  val persons: List[Person] = names.zip(ages)

But the following would be illegal.

  val persons: List[Person] = List(Bob, Laura)
  val pairs: List[(String, Int)] = persons // error

We would need an explicit _.toTuple selection to express this:

  val pairs: List[(String, Int)] = persons.map(_.toTuple)

Note that conformance rules for named tuples are analogous to the rules for named parameters. One can assign parameters by position to a named parameter list.

  def f(param: Int) = ...
  f(param = 1)   // OK
  f(2)           // Also OK

But one cannot use a name to pass an argument to an unnamed parameter:

    val f: Int => T
    f(2)         // OK
    f(param = 2) // Not OK

The rules for tuples are analogous. Unnamed tuples conform to named tuple types, but the opposite requires a conversion.

Pattern Matching

When pattern matching on a named tuple, the pattern may be named or unnamed. If the pattern is named it needs to mention only a subset of the tuple names, and these names can come in any order. So the following are all OK:

Bob match
  case (name, age) => ...

Bob match
  case (name = x, age = y) => ...

Bob match
  case (age = x) => ...

Bob match
  case (age = x, name = y) => ...

Expansion

Named tuples are in essence just a convenient syntax for regular tuples. In the internal representation, a named tuple type is represented at compile time as a pair of two tuples. One tuple contains the names as literal constant string types, the other contains the element types. The runtime representation of a named tuples consists of just the element values, whereas the names are forgotten. This is achieved by declaring NamedTuple in package scala as an opaque type as follows:

  opaque type NamedTuple[N <: Tuple, +V <: Tuple] >: V = V

For instance, the Person type would be represented as the type

NamedTuple[("name", "age"), (String, Int)]

NamedTuple is an opaque type alias of its second, value parameter. The first parameter is a string constant type which determines the name of the element. Since the type is just an alias of its value part, names are erased at runtime, and named tuples and regular tuples have the same representation.

A NamedTuple[N, V] type is publicly known to be a supertype (but not a subtype) of its value paramater V, which means that regular tuples can be assigned to named tuples but not vice versa.

The NamedTuple object contains a number of extension methods for named tuples hat mirror the same functions in Tuple. Examples are apply, head, tail, take, drop, ++, map, or zip. Similar to Tuple, the NamedTuple object also contains types such as Elem, Head, Concat that describe the results of these extension methods.

The translation of named tuples to instances of NamedTuple is fixed by the specification and therefore known to the programmer. This means that:

  • All tuple operations also work with named tuples “out of the box”.
  • Macro libraries can rely on this expansion.

Computed Field Names

The Selectable trait now has a Fields type member that can be instantiated to a named tuple.

trait Selectable:
  type Fields <: NamedTuple.AnyNamedTuple

If Fields is instantiated in a subclass of Selectable to some named tuple type, then the available fields and their types will be defined by that type. Assume n: T is an element of the Fields type in some class C that implements Selectable, that c: C, and that n is not otherwise legal as a name of a selection on c. Then c.n is a legal selection, which expands to c.selectDynamic("n").asInstanceOf[T].

It is the task of the implementation of selectDynamic in C to ensure that its computed result conforms to the predicted type T

As an example, assume we have a query type Q[T] defined as follows:

trait Q[T] extends Selectable:
  type Fields = NamedTuple.Map[NamedTuple.From[T], Q]
  def selectDynamic(fieldName: String) = ...

Assume in the user domain:

case class City(zipCode: Int, name: String, population: Int)
val city: Q[City]

Then

city.zipCode

has type Q[Int] and it expands to

city.selectDynamic("zipCode").asInstanceOf[Q[Int]]

The NamedTuple.From Type

The NamedTuple object contains a type definition

  type From[T] <: AnyNamedTuple

From is treated specially by the compiler. When NamedTuple.From is applied to an argument type that is an instance of a case class, the type expands to the named tuple consisting of all the fields of that case class. Here, fields means: elements of the first parameter section. For instance, assuming

case class City(zip: Int, name: String, population: Int)

then NamedTuple.From[City] is the named tuple

(zip: Int, name: String, population: Int)

The same works for enum cases expanding to case classes, abstract types with case classes as upper bound, alias types expanding to case classes and singleton types with case classes as underlying type (in terms of the implementation, the classSymbol of a type must be a case class).

From is also defined on named tuples. If NT is a named tuple type, then From[NT] = NT.

Pattern Matching with Named Fields in General

We allow named patterns not just for named tuples but also for case classes. For instance:

city match
  case c @ City(name = "London") => println(c.population)
  case City(name = n, zip = 1026, population = pop) => println(pop)

Named constructor patterns are analogous to named tuple patterns. In both cases

  • every name must match the name some field of the selector,
  • names can come in any order,
  • not all fields of the selector need to be matched.

This revives SIP 43, with a much simpler desugaring than originally proposed. Named patterns are compatible with extensible pattern matching simply because unapply results can be named tuples.

Operations on Named Tuples

The operations on named tuples are defined in object scala.NamedTuple. The current version of this object is listed in Appendix A.

Restrictions

The following restrictions apply to named tuples and named pattern arguments:

  1. Either all elements of a tuple or constructor pattern are named or none are named. It is illegal to mix named and unnamed elements in a tuple. For instance, the following is in error:
    val illFormed1 = ("Bob", age = 33)  // error
    
  2. Each element name in a named tuple or constructor pattern must be unique. For instance, the following is in error:
    val illFormed2 = (name = "", age = 0, name = true)  // error
    
  3. Named tuples and case classes can be matched with either named or regular patterns. But regular tuples and other selector types can only be matched with regular tuple patterns. For instance, the following is in error:
    (tuple: Tuple) match
        case (age = x) => // error
    

Use Case

As a a use case showing some advanced capabilities of named tuples (including computed field names and the From type), we show an implementation of embedded queries in Scala. For expressions that look like working with collections are instead used to directly generate a query AST that can be further optimized and mapped to a variety of query languages. The code is given in Appendix B.

Syntax Changes

The syntax of Scala is extended as follows to support named tuples and named constructor arguments:

SimpleType        ::=  ...
                    |  ‘(’ NameAndType {‘,’ NameAndType} ‘)’
NameAndType       ::=  id ':' Type

SimpleExpr        ::=  ...
                    |  '(' NamedExprInParens {‘,’ NamedExprInParens} ')'
NamedExprInParens ::=  id '=' ExprInParens

Patterns          ::=  Pattern {‘,’ Pattern}
                    |  NamedPattern {‘,’ NamedPattern}
NamedPattern      ::=  id '=' Pattern

Compatibility

Named tuple types and expressions are simply desugared to types and trees already known to Scala. The desugaring happens before the checking, so does not influence Tasty generation.

Pattern matching with named fields requires some small additions to Typer and the PatternMatcher phase. It does not change the Tasty format, though.

Backward source compatibility is partially preserved since additions to types and patterns come with new syntax that was not expressible before. When looking at tuple expressions, we have two instances of a source incompatibility:

var age: Int
(age = 1)

This was an assignment in parentheses before, and is a named tuple of arity one now. It is however not idiomatic Scala code, since assignments are not usually enclosed in parentheses.

Also, if we have

class C:
  infix def f(age: Int)
val c: C

then

c f (age = 1)

will now construct a tuple as second operand instead of passing a named parameter.

These problems can be detected and diagnosed fairly straightforwardly: When faced with a unary named tuple, try to interpret it as an assignment, and if that succeeds, issue a migration error and suggest a workaround of these kinds:

  {age = 1}     // ok
  c.f(age = 1)  // ok

Open questions

  1. What is the precise set of types and operations we want to add to NamedTuple. This could also evolve after this SIP is completed.

  2. Should there be an implicit conversion from named tuples to ordinary tuples?

Alternatives

Structural Types

We also considered to expand structural types. Structural types allow to abstract over existing classes, but require reflection or some other library-provided mechanism for element access. By contrast, named tuples have a separate representation as tuples, which can be manipulated directly. Since elements are ordered, traversals can be defined, and this allows the definition of type generic algorithms over named tuples. Structural types don’t allow such generic algorithms directly. Be could define mappings between structural types and named tuples, which could be used to implement such algorithms. These mappings would certainly become simpler if they map to/from named tuples than if they had to map to/from user-defined “HMap”s.

By contrast to named tuples, structural types are unordered and have width subtyping. This comes with the price that no natural element ordering exist, and that one usually needs some kind of dictionary structure for access. We believe that the following advantages of named tuples over structural types outweigh the loss of subtyping flexibility:

  • Better integration since named tuples and normal tuples share the same representation.
  • Better efficiency, since no dictionary is needed.
  • Natural traversal order allows the formulation of generic algorithms such as projections and joins.

Conformance

A large part of Pre-SIP discussion centered around subtyping rules, whether ordinary tuples should subtype named-tuples (as in this proposal) or vice versa or maybe no subtyping at all.

Looking at precedent in other languages it feels like we we do want some sort of subtyping for easy convertibility and an implicit conversion in the other direction. This proposal picks unnamed <: named for the subtyping and named -> unnamed for the conversion.

The discussion established that both forms of subtyping are sound. My personal opinion is that the subtyping of this proposal is both more useful and safer than the one in the other direction. There is also the problem that changing the subtyping direction would be incompatible with the current structure of Tuple and NamedTuple since for instance zip is already an inline method on Tuple so it could not be overridden in NamedTuple. To make this work requires a refactoring of Tuple to use more extension methods, and the questions whether this is feasible and whether it can be made binary backwards compatible are unknown. I personally will not work on this, if others are willing to make the effort we can discuss the alternative subtyping as well.

Addendum: Turning things around, adopting named <: unnamed for the subtyping and `unnamed -> named for the conversion leads to weaker typing with undetected errors. Consider:

type Person = (name: String, age: Int)
val bob: Person
bob.zip((firstName: String, agee: Int))

This should report a type error. But in the alternative scheme, we’d have (firstName: String, agee: Int) <: (String, Int) by subtyping and then (String, Int) -> (name: String, age: Int) by implicit naming conversion. This is clearly not what we want.

By contrast, in the implemented scheme, we will not convert (firstName: String, agee: Int) to (String, Int) since a conversion is only attempted if the expected type is a regular tuple, and in our scenario it is a named tuple instead.

My takeaway is that these designs have rather subtle consequences and any alterations would need a full implementation before they can be judged. For instance, the situation with zip was a surprise to me, which came up since I first implemented _.toTuple as a regular implicit conversion instead of a compiler adaptation.

A possibly simpler design would be to drop all conformance and conversion rules. The problem with this approach is worse usability and problems with smooth migration. Migration will be an issue since right now everything is a regular tuple. If we make it hard to go from there to named tuples, everything will tend to stay a regular tuple and named tuples will be much less used than we would hope for.

Spread Operator

An idea I was thinking of but that I did not include in this proposal highlights another potential problem with subtyping. Consider adding a spread operator * for tuples and named tuples. if x is a tuple then f(x*) is f applied to all fields of x expanded as individual arguments. Likewise, if y is a named tuple, then f(y*) is f applied to all elements of y as named arguments. Now, if named tuples would be subtypes of tuples, this would actually be ambiguous since widening y in y* to a regular tuple would yield a different call. But with the subtyping direction we have, this would work fine.

I believe tuple spread is a potentially useful addition that would fit in well with Scala. But it’s not immediately relevant to this proposal, so is left out for now.

This section should list prior work related to the proposal, notably:

FAQ

Appendix A: NamedTuple Definition

Here is the current definition of NamedTuple. This is part of the library and therefore subject to future changes and additions.

package scala
import annotation.experimental
import compiletime.ops.boolean.*

@experimental
object NamedTuple:

  opaque type AnyNamedTuple = Any
  opaque type NamedTuple[N <: Tuple, +V <: Tuple] >: V <: AnyNamedTuple = V

  def apply[N <: Tuple, V <: Tuple](x: V): NamedTuple[N, V] = x

  def unapply[N <: Tuple, V <: Tuple](x: NamedTuple[N, V]): Some[V] = Some(x)

  extension [V <: Tuple](x: V)
    inline def withNames[N <: Tuple]: NamedTuple[N, V] = x

  export NamedTupleDecomposition.{Names, DropNames}

  extension [N <: Tuple, V <: Tuple](x: NamedTuple[N, V])

    /** The underlying tuple without the names */
    inline def toTuple: V = x

    /** The number of elements in this tuple */
    inline def size: Tuple.Size[V] = toTuple.size

    // This intentionally works for empty named tuples as well. I think NnEmptyTuple is a dead end
    // and should be reverted, justy like NonEmptyList is also appealing at first, but a bad idea
    // in the end.

    /** The value (without the name) at index `n` of this tuple */
    inline def apply(n: Int): Tuple.Elem[V, n.type] =
      inline toTuple match
        case tup: NonEmptyTuple => tup(n).asInstanceOf[Tuple.Elem[V, n.type]]
        case tup => tup.productElement(n).asInstanceOf[Tuple.Elem[V, n.type]]

    /** The first element value of this tuple */
    inline def head: Tuple.Elem[V, 0] = apply(0)

    /** The tuple consisting of all elements of this tuple except the first one */
    inline def tail: Tuple.Drop[V, 1] = toTuple.drop(1)

    /** The last element value of this tuple */
    inline def last: Tuple.Last[V] = apply(size - 1).asInstanceOf[Tuple.Last[V]]

    /** The tuple consisting of all elements of this tuple except the last one */
    inline def init: Tuple.Init[V] = toTuple.take(size - 1).asInstanceOf[Tuple.Init[V]]

    /** The tuple consisting of the first `n` elements of this tuple, or all
     *  elements if `n` exceeds `size`.
     */
    inline def take(n: Int): NamedTuple[Tuple.Take[N, n.type], Tuple.Take[V, n.type]] =
      toTuple.take(n)

    /** The tuple consisting of all elements of this tuple except the first `n` ones,
     *  or no elements if `n` exceeds `size`.
     */
    inline def drop(n: Int): NamedTuple[Tuple.Drop[N, n.type], Tuple.Drop[V, n.type]] =
      toTuple.drop(n)

    /** The tuple `(x.take(n), x.drop(n))` */
    inline def splitAt(n: Int): NamedTuple[Tuple.Split[N, n.type], Tuple.Split[V, n.type]] =
      toTuple.splitAt(n)

    /** The tuple consisting of all elements of this tuple followed by all elements
     *  of tuple `that`. The names of the two tuples must be disjoint.
     */
    inline def ++ [N2 <: Tuple, V2 <: Tuple](that: NamedTuple[N2, V2])(using Tuple.Disjoint[N, N2] =:= true)
      : NamedTuple[Tuple.Concat[N, N2], Tuple.Concat[V, V2]]
      = toTuple ++ that.toTuple

    // inline def :* [L] (x: L): NamedTuple[Append[N, ???], Append[V, L] = ???
    // inline def *: [H] (x: H): NamedTuple[??? *: N], H *: V] = ???

    /** The named tuple consisting of all element values of this tuple mapped by
     *  the polymorphic mapping function `f`. The names of elements are preserved.
     *  If `x = (n1 = v1, ..., ni = vi)` then `x.map(f) = `(n1 = f(v1), ..., ni = f(vi))`.
     */
    inline def map[F[_]](f: [t] => t => F[t]): NamedTuple[N, Tuple.Map[V, F]] =
      toTuple.map(f).asInstanceOf[NamedTuple[N, Tuple.Map[V, F]]]

    /** The named tuple consisting of all elements of this tuple in reverse */
    inline def reverse: NamedTuple[Tuple.Reverse[N], Tuple.Reverse[V]] =
      toTuple.reverse

    /** The named tuple consisting of all elements values of this tuple zipped
     *  with corresponding element values in named tuple `that`.
     *  If the two tuples have different sizes,
     *  the extra elements of the larger tuple will be disregarded.
     *  The names of `x` and `that` at the same index must be the same.
     *  The result tuple keeps the same names as the operand tuples.
     */
    inline def zip[V2 <: Tuple](that: NamedTuple[N, V2]): NamedTuple[N, Tuple.Zip[V, V2]] =
      toTuple.zip(that.toTuple)

    /** A list consisting of all element values */
    inline def toList: List[Tuple.Union[V]] = toTuple.toList.asInstanceOf[List[Tuple.Union[V]]]

    /** An array consisting of all element values */
    inline def toArray: Array[Object] = toTuple.toArray

    /** An immutable array consisting of all element values */
    inline def toIArray: IArray[Object] = toTuple.toIArray

  end extension

  /** The size of a named tuple, represented as a literal constant subtype of Int */
  type Size[X <: AnyNamedTuple] = Tuple.Size[DropNames[X]]

  /** The type of the element value at position N in the named tuple X */
  type Elem[X <: AnyNamedTuple, N <: Int] = Tuple.Elem[DropNames[X], N]

  /** The type of the first element value of a named tuple */
  type Head[X <: AnyNamedTuple] = Elem[X, 0]

  /** The type of the last element value of a named tuple */
  type Last[X <: AnyNamedTuple] = Tuple.Last[DropNames[X]]

  /** The type of a named tuple consisting of all elements of named tuple X except the first one */
  type Tail[X <: AnyNamedTuple] = Drop[X, 1]

  /** The type of the initial part of a named tuple without its last element */
  type Init[X <: AnyNamedTuple] =
    NamedTuple[Tuple.Init[Names[X]], Tuple.Init[DropNames[X]]]

  /** The type of the named tuple consisting of the first `N` elements of `X`,
   *  or all elements if `N` exceeds `Size[X]`.
   */
  type Take[X <: AnyNamedTuple, N <: Int] =
    NamedTuple[Tuple.Take[Names[X], N], Tuple.Take[DropNames[X], N]]

  /** The type of the named tuple consisting of all elements of `X` except the first `N` ones,
   *  or no elements if `N` exceeds `Size[X]`.
   */
  type Drop[X <: AnyNamedTuple, N <: Int] =
    NamedTuple[Tuple.Drop[Names[X], N], Tuple.Drop[DropNames[X], N]]

  /** The pair type `(Take(X, N), Drop[X, N]). */
  type Split[X <: AnyNamedTuple, N <: Int] = (Take[X, N], Drop[X, N])

  /** Type of the concatenation of two tuples `X` and `Y` */
  type Concat[X <: AnyNamedTuple, Y <: AnyNamedTuple] =
    NamedTuple[Tuple.Concat[Names[X], Names[Y]], Tuple.Concat[DropNames[X], DropNames[Y]]]

  /** The type of the named tuple `X` mapped with the type-level function `F`.
   *  If `X = (n1 : T1, ..., ni : Ti)` then `Map[X, F] = `(n1 : F[T1], ..., ni : F[Ti])`.
   */
  type Map[X <: AnyNamedTuple, F[_ <: Tuple.Union[DropNames[X]]]] =
    NamedTuple[Names[X], Tuple.Map[DropNames[X], F]]

  /** A named tuple with the elements of tuple `X` in reversed order */
  type Reverse[X <: AnyNamedTuple] =
    NamedTuple[Tuple.Reverse[Names[X]], Tuple.Reverse[DropNames[X]]]

  /** The type of the named tuple consisting of all element values of
   *  named tuple `X` zipped with corresponding element values of
   *  named tuple `Y`. If the two tuples have different sizes,
   *  the extra elements of the larger tuple will be disregarded.
   *  The names of `X` and `Y` at the same index must be the same.
   *  The result tuple keeps the same names as the operand tuples.
   *  For example, if
   *  ```
   *     X = (n1 : S1, ..., ni : Si)
   *     Y = (n1 : T1, ..., nj : Tj)  where j >= i
   *  ```
   *  then
   *  ```
   *     Zip[X, Y] = (n1 : (S1, T1), ..., ni: (Si, Ti))
   *  ```
   *  @syntax markdown
   */
  type Zip[X <: AnyNamedTuple, Y <: AnyNamedTuple] =
    Tuple.Conforms[Names[X], Names[Y]] match
      case true =>
        NamedTuple[Names[X], Tuple.Zip[DropNames[X], DropNames[Y]]]

  type From[T] <: AnyNamedTuple

end NamedTuple

/** Separate from NamedTuple object so that we can match on the opaque type NamedTuple. */
@experimental
object NamedTupleDecomposition:
  import NamedTuple.*

  /** The names of a named tuple, represented as a tuple of literal string values. */
  type Names[X <: AnyNamedTuple] <: Tuple = X match
    case NamedTuple[n, _] => n

  /** The value types of a named tuple represented as a regular tuple. */
  type DropNames[NT <: AnyNamedTuple] <: Tuple = NT match
    case NamedTuple[_, x] => x

Appendix B: Embedded Queries Case Study

import language.experimental.namedTuples
import NamedTuple.{NamedTuple, AnyNamedTuple}

/* This is a demonstrator that shows how to map regular for expressions to
 * internal data that can be optimized by a query engine. It needs NamedTuples
 * and type classes but no macros. It's so far very provisional and experimental,
 * intended as a basis for further exploration.
 */

/** The type of expressions in the query language */
trait Expr[Result] extends Selectable:

  /** This type is used to support selection with any of the field names
   *  defined by Fields.
   */
  type Fields = NamedTuple.Map[NamedTuple.From[Result], Expr]

  /** A selection of a field name defined by Fields is implemented by `selectDynamic`.
   *  The implementation will add a cast to the right Expr type corresponding
   *  to the field type.
   */
  def selectDynamic(fieldName: String) = Expr.Select(this, fieldName)

  /** Member methods to implement universal equality on Expr level. */
  def == (other: Expr[?]): Expr[Boolean] = Expr.Eq(this, other)
  def != (other: Expr[?]): Expr[Boolean] = Expr.Ne(this, other)

object Expr:

  /** Sample extension methods for individual types */
  extension (x: Expr[Int])
    def > (y: Expr[Int]): Expr[Boolean] = Gt(x, y)
    def > (y: Int): Expr[Boolean] = Gt(x, IntLit(y))
  extension (x: Expr[Boolean])
    def &&(y: Expr[Boolean]): Expr[Boolean] = And(x, y)
    def || (y: Expr[Boolean]): Expr[Boolean] = Or(x, y)

  // Note: All field names of constructors in the query language are prefixed with `$`
  // so that we don't accidentally pick a field name of a constructor class where we want
  // a name in the domain model instead.

  // Some sample constructors for Exprs
  case class Gt($x: Expr[Int], $y: Expr[Int]) extends Expr[Boolean]
  case class Plus(x: Expr[Int], y: Expr[Int]) extends Expr[Int]
  case class And($x: Expr[Boolean], $y: Expr[Boolean]) extends Expr[Boolean]
  case class Or($x: Expr[Boolean], $y: Expr[Boolean]) extends Expr[Boolean]

  // So far Select is weakly typed, so `selectDynamic` is easy to implement.
  // Todo: Make it strongly typed like the other cases
  case class Select[A]($x: Expr[A], $name: String) extends Expr

  case class Single[S <: String, A]($x: Expr[A])
  extends Expr[NamedTuple[S *: EmptyTuple, A *: EmptyTuple]]

  case class Concat[A <: AnyNamedTuple, B <: AnyNamedTuple]($x: Expr[A], $y: Expr[B])
  extends Expr[NamedTuple.Concat[A, B]]

  case class Join[A <: AnyNamedTuple](a: A)
  extends Expr[NamedTuple.Map[A, StripExpr]]

  type StripExpr[E] = E match
    case Expr[b] => b

  // Also weakly typed in the arguents since these two classes model universal equality */
  case class Eq($x: Expr[?], $y: Expr[?]) extends Expr[Boolean]
  case class Ne($x: Expr[?], $y: Expr[?]) extends Expr[Boolean]

  /** References are placeholders for parameters */
  private var refCount = 0

  case class Ref[A]($name: String = "") extends Expr[A]:
    val id = refCount
    refCount += 1
    override def toString = s"ref$id(${$name})"

  /** Literals are type-specific, tailored to the types that the DB supports */
  case class IntLit($value: Int) extends Expr[Int]

  /** Scala values can be lifted into literals by conversions */
  given Conversion[Int, IntLit] = IntLit(_)

  /** The internal representation of a function `A => B`
   *  Query languages are ususally first-order, so Fun is not an Expr
   */
  case class Fun[A, B](param: Ref[A], f: B)

  type Pred[A] = Fun[A, Expr[Boolean]]

  /** Explicit conversion from
   *      (name_1: Expr[T_1], ..., name_n: Expr[T_n])
   *  to
   *      Expr[(name_1: T_1, ..., name_n: T_n)]
   */
  extension [A <: AnyNamedTuple](x: A) def toRow: Join[A] = Join(x)

  /** Same as _.toRow, as an implicit conversion */
  given [A <: AnyNamedTuple]: Conversion[A, Expr.Join[A]] = Expr.Join(_)

end Expr

/** The type of database queries. So far, we have queries
 *  that represent whole DB tables and queries that reify
 *  for-expressions as data.
 */
trait Query[A]

object Query:
  import Expr.{Pred, Fun, Ref}

  case class Filter[A]($q: Query[A], $p: Pred[A]) extends Query[A]
  case class Map[A, B]($q: Query[A], $f: Fun[A, Expr[B]]) extends Query[B]
  case class FlatMap[A, B]($q: Query[A], $f: Fun[A, Query[B]]) extends Query[B]

  // Extension methods to support for-expression syntax for queries
  extension [R](x: Query[R])

    def withFilter(p: Ref[R] => Expr[Boolean]): Query[R] =
      val ref = Ref[R]()
      Filter(x, Fun(ref, p(ref)))

    def map[B](f: Ref[R] => Expr[B]): Query[B] =
      val ref = Ref[R]()
      Map(x, Fun(ref, f(ref)))

    def flatMap[B](f: Ref[R] => Query[B]): Query[B] =
      val ref = Ref[R]()
      FlatMap(x, Fun(ref, f(ref)))
end Query

/** The type of query references to database tables */
case class Table[R]($name: String) extends Query[R]

// Everything below is code using the model -----------------------------

// Some sample types
case class City(zipCode: Int, name: String, population: Int)
type Address = (city: City, street: String, number: Int)
type Person = (name: String, age: Int, addr: Address)

@main def Test =

  val cities = Table[City]("cities")

  val q1 = cities.map: c =>
    c.zipCode
  val q2 = cities.withFilter: city =>
      city.population > 10_000
    .map: city =>
      city.name

  val q3 =
    for
      city <- cities
      if city.population > 10_000
    yield city.name

  val q4 =
    for
      city <- cities
      alt <- cities
      if city.name == alt.name && city.zipCode != alt.zipCode
    yield
      city

  val addresses = Table[Address]("addresses")
  val q5 =
    for
      city <- cities
      addr <- addresses
      if addr.street == city.name
    yield
      (name = city.name, num = addr.number)

  val q6 =
    cities.map: city =>
      (name = city.name, zipCode = city.zipCode)

  def run[T](q: Query[T]): Iterator[T] = ???

  def x1: Iterator[Int] = run(q1)
  def x2: Iterator[String] = run(q2)
  def x3: Iterator[String] = run(q3)
  def x4: Iterator[City] = run(q4)
  def x5: Iterator[(name: String, num: Int)] = run(q5)
  def x6: Iterator[(name: String, zipCode: Int)] = run(q6)