3

Generalized Algebraic Datatypes in Scala 3

 3 years ago
source link: https://blog.oyanglul.us/scala/dotty/en/gadt
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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: 
6: enum SafeList[+A, +S <: Size] {
7:   case Nil extends SafeList[Nothing, Size.Empty.type] // <-
8:   case Cons(head: A, tail: SafeList[A, Size]) extends SafeList[A, Size.NonEmpty.type]
9: }

What GATD provides fine control of type, i.e. line 7 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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK