Algebraic Data Types & GADTs
|
This content was generated with the assistance of AI and should be verified against the official documentation before being relied on in production. The reference material consulted while preparing these pages is listed in the section bibliography. |
This page is written against Scala 3.10 (3.10.0, released 2026-10-12) and every example was compiled and run with Scala
3.10.0 through Scala CLI on JDK 26 (checked on 2026-10-15). Algebraic data types have not changed since Scala 3.0, so
everything here also works on the 3.9 LTS line (3.9.0, 2026-09-03) and on the 3.3 LTS line; the three samples that
matter most (the Segment enum, the covariant Maybe enum and the GADT evaluator) were also re-run with
//> using scala 3.9.0 and printed the same output. Nothing on this page needs a library beyond the standard library.
An algebraic data type (ADT) is a way of describing data as a closed set of alternatives, each of which is a group of
fields. The "algebra" is the observation that the two ways of combining types behave like sums and products: a
product type holds a value of each of its components at once (a case class, a tuple), and a sum type holds a value
of exactly one of several alternatives (an enum, a sealed trait with subclasses). Because the set of alternatives
is closed, the compiler can check that a match handles every one. The examples use the trailhead scenario, a toolkit
that plans hikes on a network of mountain trails. For the building blocks see Case Classes,
Enums and Pattern Matching; for the same ideas on neighbouring
languages see Kotlin sealed classes and enums and
Java records and sealed classes.
Sum and product types
The names come from counting the possible values. A Boolean has 2 values and a Unit has 1. A pair (Boolean, Boolean)
has 2 x 2 = 4 values, so a tuple or case class multiplies the value counts of its fields: that is a product. An
Either[Boolean, Unit] has 2 + 1 = 3 values (Left(true), Left(false), Right(())), so a type that offers a choice adds the
value counts of its alternatives: that is a sum. Scala 3 spells these shapes in two equivalent ways.
| Shape | With enum |
With sealed trait |
|---|---|---|
Product |
|
|
Sum |
The enum itself, with each |
The sealed trait, with the subclasses and objects that extend it as alternatives |
Unit-like alternative (a product of zero fields) |
|
|
Everything in the following sections is a combination of these: a sum whose alternatives are products, products whose fields are themselves sums, and so on, possibly referring to the type being defined.
enum ADTs
The shortest way to declare an ADT is an enum whose cases carry parameters. The cases of the example below form a tree:
a route is either a flat leg, a climb, or two routes joined end to end, and the last case holds two further routes.
//> using scala 3.10.0
package trailhead
// A route is either a single leg or two routes joined end to end.
enum Segment:
case Flat(name: String, lengthKm: Double)
case Climb(name: String, lengthKm: Double, ascentM: Int)
case Joined(first: Segment, second: Segment)
import Segment.*
def lengthKm(s: Segment): Double = s match
case Flat(_, km) => km
case Climb(_, km, _) => km
case Joined(a, b) => lengthKm(a) + lengthKm(b)
def ascentM(s: Segment): Int = s match
case Flat(_, _) => 0
case Climb(_, _, up) => up
case Joined(a, b) => ascentM(a) + ascentM(b)
@main def run(): Unit =
val route = Joined(Flat("Valley", 4.0), Joined(Climb("Ridge", 3.5, 600), Flat("Plateau", 2.0)))
println(s"${lengthKm(route)} km, ${ascentM(route)} m up")
println(route)
println(Flat("a", 1.0) == Flat("a", 1.0))
println(route.isInstanceOf[Segment])
println(Climb("Ridge", 3.5, 600).ordinal)9.5 km, 600 m up
Joined(Flat(Valley,4.0),Joined(Climb(Ridge,3.5,600),Flat(Plateau,2.0)))
true
true
1Each case with a parameter list becomes a final case class, so it gets equals, hashCode, toString, copy and an
extractor for free, and every case also has an ordinal index (here Climb is 1). The whole value is a tree, drawn below;
the diagram shows Segment as the sum and the three cases as its alternatives, with Joined pointing back at Segment.
A match over the cases is the only thing needed to consume the data. The functions lengthKm and ascentM are
total: they return a value for every possible Segment. This is the practical payoff of a closed sum, discussed in
Exhaustivity checking.
sealed trait hierarchies
An enum is a convenience; the same ADT can be written out as a sealed trait (or sealed abstract class) plus case
classes and case objects. This is the only form Scala 2 had, and it remains the right choice when the cases need their own
class bodies, when they must extend different classes, or when the code must also compile on Scala 2.
//> using scala 3.10.0
// The same idea as a sealed trait hierarchy.
sealed trait Leg
final case class Flat(name: String, lengthKm: Double) extends Leg
final case class Climb(name: String, lengthKm: Double, ascentM: Int) extends Leg
case object Rest extends Leg
def km(l: Leg): Double = l match
case Flat(_, k) => k
case Climb(_, k, _) => k
@main def run(): Unit =
println(km(Flat("a", 2.0)))
val legs = List(Flat("a", 1.0), Climb("b", 2.0, 100))
println(legs)
val inferred = List(Flat("a", 1.0), Rest)
val t: Int = inferredThe km function forgets Rest on purpose, and the last line is a deliberate type error to show what the compiler infers. The
compiler output (the example above, minus the last two lines, ran and printed the two lines after the warning):
[warn] ./a2ok.scala:9:26
[warn] match may not be exhaustive.
[warn]
[warn] It would fail on pattern case: Rest
[warn] def km(l: Leg): Double = l match
[warn] ^
2.0
List(Flat(a,1.0), Climb(b,2.0,100))[error] ./a2.scala:18:16
[error] Found: (inferred : List[Leg])
[error] Required: Int
[error] val t: Int = inferred
[error] ^^^^^^^^Three rules make the hierarchy a closed sum:
-
sealedallows direct subclasses only in the same source file (the compilation unit); anywhere else is error E112, "Unable to Extend Sealed Class". Top-level definitions let a sealed trait and its subclasses sit next to each other without a wrapping object. -
The subclasses should be
final(orsealed, or enum cases), otherwise somebody could still extend them in the same file and the "all alternatives" guarantee gets weaker. A case class that is notfinalis still allowed. -
The inferred type of a list holding a
FlatandRestisList[Leg], the sealed trait itself (see the compiler error above). Scala 2 inferredList[Product with Leg with Serializable], which is why Scala 2 code often addsextends Product with Serializableto the sealed trait; the idiom is not needed in Scala 3 and writing it anyway is harmless.
Exhaustivity checking
Because the alternatives are known, the compiler checks match expressions on an ADT. A missing case is a warning,
not an error, in Scala 3.10 (the -Werror option, formerly -Xfatal-warnings, turns it into a build failure). The enum version
of the example above warns in the same way and fails at run time:
//> using scala 3.10.0
enum Leg:
case Flat(name: String, lengthKm: Double)
case Climb(name: String, lengthKm: Double, ascentM: Int)
case Rest
def km(l: Leg): Double = l match
case Leg.Flat(_, k) => k
case Leg.Climb(_, k, _) => k
@main def run(): Unit =
println(km(Leg.Rest))[warn] ./a3.scala:8:26
[warn] match may not be exhaustive.
[warn]
[warn] It would fail on pattern case: Rest
[warn] def km(l: Leg): Double = l match
[warn] ^
Exception in thread "main" scala.MatchError: Rest (of class Leg$$anon$1)
at a3$package$.km(a3.scala:10)
at a3$package$.run(a3.scala:13)
at run.main(a3.scala:12)The check is the reason ADTs are preferred over open class hierarchies: when you add a new alternative to the ADT, every
match that is now incomplete shows up as a warning at compile time. Guards (case X if cond) are treated as possibly
false, so a match that is only complete because of a guard needs a final unguarded case. The checking rules and the
@unchecked annotation are covered in Pattern Matching.
Constructor proxies and widened types
A call such as Flat("Valley", 4.0) on an enum case does not return a Flat: the type of the result is widened to the enum
type, Segment. This is a deliberate rule of the enum desugaring (see below), because for ADTs the useful type of a
value is almost always the sum, and a narrow type makes inferred collections and conditionals needlessly specific. The
case class’s own type is still available when you ask for it with new, and the narrow type keeps copy and the field
accessors.
//> using scala 3.10.0
enum Segment:
case Flat(name: String, lengthKm: Double)
case Rest
import Segment.*
@main def run(): Unit =
val f = Flat("Valley", 4.0) // inferred type: Segment
val g = new Flat("Valley", 4.0) // inferred type: Segment.Flat
println(g.copy(lengthKm = 5.0))
println(g.name)
println(f.ordinal)
println(Rest.ordinal)
println(f.name)The last line does not compile on f, because the field accessor is a member of the case class only:
[error] ./a11.scala:16:11
[error] value name is not a member of Segment
[error] println(f.name)
[error] ^With that line removed the example prints:
Flat(Valley,5.0)
Valley
0
1In practice the widening is rarely a nuisance: you match on the Segment, which gives access to the fields, and
non-enum case classes keep their narrow type. If a function needs the specific case, declare the parameter type
Segment.Flat, or construct with new.
Variance of enum cases
An enum can take type parameters, and the variance annotation (+T for covariant, -T for contravariant) works exactly as it
does for classes (see Variance). A covariant ADT lets the empty case be shared by every instantiation:
//> using scala 3.10.0
enum Maybe[+T]:
case Just(value: T)
case Absent
import Maybe.*
def orElse[T](m: Maybe[T], default: T): T = m match
case Just(v) => v
case Absent => default
@main def run(): Unit =
val a = Just(1)
val b = Absent
val xs = List(Just(1), Just(two))
val n: Maybe[Int] = Absent
println(a)
println(b)
println(xs)
println(orElse(n, -1))
println(orElse(Just(5), -1))Just(1)
Absent
List(Just(1), Just(two))
-1
5The inferred types, from compiler errors when assigning each value to an Int (an extra experiment, not part of the program):
Found: (a : Maybe[Int])
Found: (b : Maybe[Nothing])
Found: (xs : List[Maybe[Int | String]])The simple case Absent expands to a case that extends Maybe[Nothing]: for a covariant parameter the compiler picks
the lower bound (Nothing), and for a contravariant parameter it picks the upper bound (Any). A Maybe[Nothing] is
a subtype of every Maybe[T], so Absent fits wherever a Maybe[Int] is wanted, as val n shows. The list of mixed
Just values widens to Maybe[Int | String] through the union type (see Union & Intersection Types).
If the type parameter is invariant (no variance annotation) the compiler has nothing to choose, so a simple case is rejected with a message that names the problem:
//> using scala 3.10.0
enum Box[T]:
case Full(value: T)
case Empty[error] ./a5.scala:5:3
[error] cannot determine type argument for enum parent class Box,
[error] type parameter T is invariant
[error] case Empty
[error] ^^^^^^^^^^There are two repairs: make the parameter covariant, or give the case an explicit extends clause (a value case), as in
case Empty extends Box[Nothing], which is accepted for the invariant Box[T] and compiled and ran in the same session.
Recursive ADTs
An ADT may refer to itself in a field, and that is how lists, trees and expression languages are built. The Segment.Joined
case above is already recursive. The example below is a complete minimal immutable list, covariant like the standard
library’s List, with functions written as extension methods.
//> using scala 3.10.0
// A recursive, covariant ADT: a minimal immutable list.
enum Stops[+A]:
case Cons(head: A, tail: Stops[A])
case End
import Stops.*
extension [A](s: Stops[A])
def length: Int = s match
case Cons(_, t) => 1 + t.length
case End => 0
def foldRight[B](z: B)(f: (A, B) => B): B = s match
case Cons(h, t) => f(h, t.foldRight(z)(f))
case End => z
@main def run(): Unit =
val names: Stops[String] = Cons("Refugio", Cons("Pico", End))
println(names.length)
println(names.foldRight("")((n, acc) => n.take(1) + acc))
val mixed: Stops[Any] = Cons(1, names)
println(mixed)
println(End.length)2
RP
Cons(1,Cons(Refugio,Cons(Pico,End)))
0End is a Stops[Nothing], so it can end a list of any element type, and the Stops[String] can be used where a
Stops[Any] is expected. Structural recursion on the ADT (one match case per alternative, a recursive call per
recursive field) is the standard way to write a function over it. Deeply recursive functions like length use stack
space proportional to the size; see Recursion & Tail Calls.
The enum desugaring rules
An enum is syntax: the compiler rewrites it into a sealed abstract class and a companion object using nine rules. Knowing
them explains the behaviour seen so far (widened types, ordinal, the invariance error, why values exists). A summary
of the Scala 3 Reference page:
| Rule | Effect |
|---|---|
1 |
|
2 |
|
3 |
A simple case |
4 |
A simple case of an enum with type parameters expands to |
5 |
A class case without an |
6 |
In a generic enum, a class case with no type parameters and no |
7 |
A class case with an |
8 |
A value case |
9 |
A class case becomes a |
The companion also gets values and valueOf when the enum has singleton cases, and the generated apply and copy of a
class case are treated specially: a call is given the type of the parents (P1 & ... & Pn) when that is compatible with
the expected type, which is the widening seen above. A hand-written version of a small enum, simplified, is below.
//> using scala 3.10.0
// Roughly what the compiler generates for this enum (simplified, hand-written):
// enum Seg:
// case Flat(name: String, km: Double)
// case Rest
sealed abstract class Seg extends scala.reflect.Enum
object Seg:
final case class Flat(name: String, km: Double) extends Seg:
def ordinal: Int = 0
case object Rest extends Seg:
def ordinal: Int = 1
@main def run(): Unit =
val s: Seg = Seg.Flat("Valley", 4.0)
println(s.ordinal)
println(Seg.Rest.ordinal)
println(s)
println(Seg.Rest)
println(s.isInstanceOf[scala.reflect.Enum])0
1
Flat(Valley,4.0)
Rest
trueThe real expansion differs in details (singleton cases are anonymous-class values created by $new, the apply
methods are widened, and productPrefix and toString are generated), but the structure is the same. The real
generated classes, observed with getClass, behave as the rules say: for an all-singleton enum Plain with cases A and
B, Plain.values.toList prints List(A, B), Plain.valueOf("B") prints B, Plain.A.getClass is the anonymous
class Plain$$anon$2, and a class case such as Shape.Circle(1.0) has ordinal 0, productPrefix Circle and getClass.getSuperclass
equal to the enum class Shape.
One difference between the reference page and the compiler is worth knowing. The page says an enum that defines one or more singleton
cases gets values and valueOf. When an enum mixes singleton cases with class cases, Scala 3.10.0 reports values
as missing instead:
[error] value values is not a member of object Level.
[error] Although class Level is an enum, it has non-singleton cases,
[error] meaning a values array is not definedUse an enum with only simple cases when you need values, and a separate list of the singleton cases when you do not.
Generalized algebraic data types
A generalized algebraic data type (GADT) is an ADT where each case may fix the type parameter of the whole type to
something more specific. The type of the value then tells you which alternative you may have, and a match that refines
the type in each branch can return a result of the exact type. The standard use is a typed expression language, where
integer expressions evaluate to Int, comparisons to Boolean, and ill-typed combinations do not compile.
//> using scala 3.10.0
// A small expression language whose type parameter tracks the result type.
enum Expr[T]:
case IntLit(value: Int) extends Expr[Int]
case BoolLit(value: Boolean) extends Expr[Boolean]
case Add(left: Expr[Int], right: Expr[Int]) extends Expr[Int]
case Less(left: Expr[Int], right: Expr[Int]) extends Expr[Boolean]
case If[A](cond: Expr[Boolean], yes: Expr[A], no: Expr[A]) extends Expr[A]
case Pair[A, B](first: Expr[A], second: Expr[B]) extends Expr[(A, B)]
case Fst[A, B](pair: Expr[(A, B)]) extends Expr[A]
import Expr.*
def eval[T](e: Expr[T]): T = e match
case IntLit(n) => n // T is Int here
case BoolLit(b) => b // T is Boolean here
case Add(l, r) => eval(l) + eval(r)
case Less(l, r) => eval(l) < eval(r)
case If(c, y, n) => if eval(c) then eval(y) else eval(n)
case Pair(a, b) => (eval(a), eval(b))
case Fst(p) => eval(p)._1
@main def run(): Unit =
val e = If(Less(IntLit(2), Add(IntLit(1), IntLit(3))), Pair(IntLit(10), BoolLit(true)), Pair(IntLit(0), BoolLit(false)))
println(eval(e))
println(eval(Fst(e)))
println(eval(Less(IntLit(5), IntLit(1))))(10,true)
10
falseThe key line is case IntLit(n) => n. The method’s return type is the abstract T, and n is an Int. This compiles because
matching on IntLit proves that e has type Expr[Int], so inside the branch the compiler records the GADT
constraint T = Int and accepts an Int where a T is required. Each branch has its own constraint, and the constraints do not
leak between branches. Without this refinement eval could not have the single signature Expr[T] => T; the usual Scala 2 or Java encoding
needs an unchecked cast per case.
The case parameters carry types that make bad programs impossible. The If case uses the same A for both
branches, Pair and Fst pass the component types through, and the compiler rejects wrong code both inside the
evaluator and at the use sites:
//> using scala 3.10.0
enum Expr[T]:
case IntLit(value: Int) extends Expr[Int]
case BoolLit(value: Boolean) extends Expr[Boolean]
case Add(left: Expr[Int], right: Expr[Int]) extends Expr[Int]
import Expr.*
def wrong[T](e: Expr[T]): T = e match
case IntLit(n) => "oops"
case BoolLit(b) => b
case Add(l, r) => 0
val ill = Add(IntLit(1), BoolLit(true))[error] ./a8.scala:11:22
[error] Found: ("oops" : String)
[error] Required: T
[error]
[error] where: T is a type in method wrong which is an alias of Int
[error] case IntLit(n) => "oops"
[error] ^^^^^^
[error] ./a8.scala:15:26
[error] Found: Expr.BoolLit
[error] Required: Expr[Int]
[error] val ill = Add(IntLit(1), BoolLit(true))
[error] ^^^^^^^^^^^^^The first error message reveals the mechanism: inside the IntLit branch T is "an alias of Int". The BoolLit(b) => b
and Add(l, r) => 0 branches were accepted by the same constraint solver.
GADTs with sealed traits
GADTs do not need enum. A sealed trait whose subclasses fix the type parameter gives the same result, which is useful for
a command or request type whose subclasses each know their reply type.
//> using scala 3.10.0
// Same idea with a sealed trait: the subclasses fix the type parameter.
sealed trait Cmd[R]
case class Count(prefix: String) extends Cmd[Int]
case class Names(prefix: String) extends Cmd[List[String]]
case object Ping extends Cmd[Boolean]
val data = List("alpine", "alps", "valley")
def execute[R](c: Cmd[R]): R = c match
case Count(p) => data.count(_.startsWith(p))
case Names(p) => data.filter(_.startsWith(p))
case Ping => true
@main def run(): Unit =
println(execute(Count("al")))
println(execute(Names("al")))
println(execute(Ping))2
List(alpine, alps)
trueCallers get a result whose static type depends on the command: execute(Count("al")) is an Int and no cast is needed.
The type refinement happens inside the branches of a pattern match, where the compiler knows which case was matched.
Describing alternatives in domain models
The Scala 3 Book’s functional modeling chapter uses ADTs to describe the alternatives of a domain, and Scala offers several tools that cover similar ground. A quick guide to choosing between them:
//> using scala 3.10.0
// Alternatives in the domain: ADT vs. union type vs. Either.
enum Contact:
case Email(address: String)
case Phone(number: String)
case Nobody
def reach(c: Contact): String = c match
case Contact.Email(a) => s"mail $a"
case Contact.Phone(n) => s"call $n"
case Contact.Nobody => "no contact"
case class Phone(number: String)
case class Email(address: String)
def reachUnion(c: Email | Phone): String = c match
case Email(a) => s"mail $a"
case Phone(n) => s"call $n"
def parse(s: String): Either[String, Int] = s.toIntOption.toRight(s"not a number: $s")
@main def run(): Unit =
println(reach(Contact.Email("a@localhost")))
println(reachUnion(Phone("555")))
println(parse("12"))
println(parse("x"))
val xs = List(Contact.Email("a@localhost"), Contact.Nobody)
println(xs)mail a@localhost
call 555
Right(12)
Left(not a number: x)
List(Email(a@localhost), Nobody)| Tool | Use when | Caveats |
|---|---|---|
|
The alternatives are owned by your domain, form a named concept ( |
Adding a case is a source change in one file. Cases are not independent types by default (constructor proxies return the enum type). |
Union type |
The alternatives already exist as unrelated types and you only need to accept either, with no new supertype. |
No new type name, no |
|
A result that is one of two things, typically a failure or a value. |
The alternatives are positional ( |
|
A value that may be absent. |
A two-alternative ADT with a covariant parameter, comparable to the |
Compared with other languages
-
Scala 2. There is no
enumkeyword for ADTs; the encoding issealed traitpluscase classandcase object, often withextends Product with Serializableso that lists of cases infer a useful type. Scala 2 GADTs use the same encoding. Scala 3 enums and the constructor widening of enum cases are the main additions. -
Java. Java 17 sealed interfaces plus records (and pattern matching for
switch, final in Java 21) express the same sums and products; see Java records and sealed classes. Java records are products; sealed interfaces are the sums. Java has no GADT type refinement of that kind. -
Kotlin.
sealed classandsealed interfacewithdata classandobjectsubclasses map to the Scala encoding; see Kotlin sealed classes and enums. Kotlinenum classis a fixed set of singletons only; its payload-carrying alternative is the sealed hierarchy.
Where the books and older material are outdated
-
Scala 2 material says that the sealed trait needs
Product with Serializableto infer a good type; Scala 3 does not. -
Some older write-ups say a non-exhaustive match is an error. It is a warning in the default configuration of 3.10.
-
The reference page for the enum translation says singleton cases produce
valuesandvalueOf; as shown above, 3.10.0 rejectsvalueson an enum that also has class cases.
Scala 3.9 LTS versus 3.10
Nothing on this page differs between 3.9 and 3.10: the enum, the sealed hierarchy, the widened constructor proxies, the variance rules, the desugaring and the GADT type refinement are all Scala 3.0 features. The release notes of 3.9 and 3.10 list no change to them.