HOME | EDIT | RSS | INDEX | ABOUT | GITHUB

Generalized Algebraic Datatypes in Scala 3

中文 | English

I'm recently migrating some libs and projects to Scala 3, I guess it would be very helpful to me or anyone interested to learn some new functional programming features that Scala 3 is bringing to us.

Source code 👉 https://github.com/jcouyang/meow

ADTAlgebraic Datatypes is something that has multiple constructors return single type: 

enum List[+A]:
  case Nil
  case Cons(head: A, tail: List[A])

Here both Nil and Cons can create a value of type List[A].

This is great improvement from Scala 2, since defining an ADT is much easier than before: 

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[A](head: A, tail: List[A]) extends List[A]

But actually the way Scala 2 using is GADTGeneralized Algebraic Datatypes.

We can also do GADT using enum https://dotty.epfl.ch/docs/reference/enums/adts.html , for instance to define a SafeList: https://wiki.haskell.org/Generalised_algebraic_datatype#Example_with_lists 

1: enum Size:
2:   case Empty
3:   case NonEmpty
4: 
5: enum SafeList[+A, +S <: Size]:
6:   case Nil extends SafeList[Nothing, Size.Empty.type] // <-
7:   case Cons(head: A, tail: SafeList[A, Size]) extends SafeList[A, Size.NonEmpty.type]

What GATD provides fine control of type, i.e. line 6 no longer returns List[Nothing], we can let it return something else SafeList[Nothing, Size.Empty.type]

Same way we can make Cons return SafeList[A, Size.NonEmpty.type], which tag it as NonEmpty at type level.

So we can simply write a method safeHead just handle NonEmpty List, and it is safe at compile time. 

import SafeList._

def safeHead[A](list: SafeList[A, Size.NonEmpty.type]): A = list match
  case SafeList.Cons(head, tail) => head

When a Nil is passed to safeHead, compiler will point it out: 

safeHead(Nil)

Found:    (Main.SafeList.Nil : Main.SafeList[Nothing, (Main.Size.Empty : Main.Size)])
Required: Main.SafeList[Any, (Main.Size.NonEmpty : Main.Size)]

Try it online at Scastie: https://scastie.scala-lang.org/jcouyang/yGQTSUJ6SN2P2oUsfWu9zw/1 Or clone the repo and sbt test: https://github.com/jcouyang/meow

Footnotes:

1

https://dotty.epfl.ch/docs/reference/enums/adts.html

2

https://wiki.haskell.org/Generalised_algebraic_datatype#Example_with_lists