I know Scala 3 is not there yet. But Dotty is, and it is getting closer and closer to be Scala 3. As a Scala developer, brace yourself to something new. Similar, yet new. And in the context of pure Functional Programming, where are we heading to ? In this article I try to show some code, to foresee the future. Spoiler: it is bright !

The case

To get a sneak peek of a language, I often like to try to implement a small function. In this article, the goal will be to write a function which will zip elements of two linked lists with the following requirements:

• a list structure is immutable
• zipping two empty lists returns an empty list
• zipping two list of different sizes does not compile

A possible implementation...

Encoding a Linked List structure

Dotty aka Scala 3 brings a new enum construct. This feature enables (Generalized) Algebraic Data Types ((G)ADTs). If we mimick List from the standard library we can write this:

enum LkList[+A] {
    case Cons(head: A, tail: LkList[A]) 
    case Nil
}

In a way, enum replaces the sealed abstract class and sealed trait constructs. This syntax is more concise than before.

Encoding functor

One of the highlights of Dotty is the revamp of implicits. Today, in Scala 2, implicits have (too) many usages. Martin Odersky acknowledged this fact several times, and particularly in this talk. Dotty introduces a bunch of new keywords/syntax to address the specific case of typeclasses.

We can now define Functor as such:

trait Functor[F[_]] {
    def [A,B] (x: F[A]) map (f: A => B): F[B]
}

This is very similar to the Scala 2 encoding exept for one thing: the map function is defined as an extension method. What it says is that the map function will be available on any instance of type F given an instance of Functor for it. In Scala 2, we had to provide an implicit class to do this kind of extensions. Dotty removes this and adds some clarity.

Now, let's write an instance of Functor for our previously defined LkList .

package eu.enhan.fp.instances 

given listFunctor as Functor[LkList] {

    def [A, B] (l: LkList[A]) map (f: A => B) = l match {
        case LkList.Nil => LkList.Nil
        case LkList.Cons(h, t) => LkList.Cons(f(h), t.map(f))
    }

}

Again, Dotty brings a new syntax with a given keyword. in this case, we declare a named instance called listFunctor which is a Functor for LkList. The syntax is under heavy discussion but the debates should end with a similar syntax. The key point here is that listFunctor is clearly marked as a typeclass instance.

The next thing is to write a function needing a functor. Just to proof it, let's just write a function which only perform an addition to the element of a list (or any type for which we can implement Functor:

import eu.enhan.fp.instances.given

def plus3[F[_]: Functor](l: F[Int]) = l.map(_+3)

Dotty allows context bounds such as Scala 2, to specify required typeclasses implementations. In this case, we are specifying that there is an instance of Functor for type F for plus3 to compile. The assiduous reader would have notice a special import statement. In Scala 2 imports used to import all kind of definitions, including implicit instances. In dotty, a special treatment is given to given instances, and we have to import them explicitly using the import path.to.package.given. This ends the package object including an implicit object technique.

To explicitly summon the functor instance, we can use the using keyword (since Dotty 0.22.0-RC1) !):

import eu.enhan.fp.instances.given
def plus2[F[_]](l: F[Int])(using FF: Functor[F]): F[Int] = l.map(_+ 2)

Obviously in this example, the using directive is useless. Dotty comes with a function similar to implicitly[T] in Scala 2. Its name is summon[T].

Checking the size at compile time

Scala 3 will also be better at typelevel programming. We now add the size of the list as part of the type. This is a feature we find in Idris. This was already possible in Scala 2, with some libraries (such as Singleton-ops), but Dotty makes this accessible to anyone (well, everyone versed into typelevel programming). Let's adopt the same name as Idris for our sized linked list : Vect.

Similarly to LkList before, we are going to use enum to model the GADT:

import scala.compiletime.ops.int._

enum Vect[+A, S<:Int]{

    case Empty extends Vect[Nothing, 0] 

    case Cons(h: A, t: Vect[A, S]) extends Vect[A, S + 1] 

    def ::[B >: A](e: B): Vect[B, S + 1] = Cons(e, this)
 
}

object Vect {
    def apply[A](e: A): Vect[A, 1] = e :: Empty
}

The first line is very important: it brings in scope typelevel operators on int types. A lot of work has been done on SIP-23 to implement Singleton types (types which are inhabited by only one possible value). Dotty allows us to compute new types from existing ones. In our case, we define Vect to be a type constructor with two parameters A (the type of the elements in the Vect) and S (the size of the Vect). Like LkList we define two cases:

• an empty vector is a Vect with elements of type Nothing and a size of 0
• The Cons constructor builds a new Vect by prepending an element to a Vect. We can see that the size type parameter is increased by one, updating the size at the typelevel.

Here is how we could use such a type:

val v = 4 :: 3 :: 2 :: Vect(2)
// Type of v is: Vect[Int, 4]
println(v)
// outputs : Cons(4,Cons(3,Cons(2,Cons(2,Empty))))

Defining the headOption function to return an Option corresponding to the head of the vector resulted in encountering this bug but Guillaume Martres gave me a workaround to implement this function as an extension.

// in companion object Vect :
def [A, S <: Int] (v: Vect[A, S]) headOption = v match {
    case Empty => None
    case Cons(h, t) => Some(h) 
}

In the same way, it was easy to define a map function:

def [A, B, S <: Int] (v: Vect[A, S]) map(f: A => B) : Vect[B, S] = v match {
    case Empty => Empty
    case Cons(h,t) => Cons(f(h), t.map(f))
}

One of the important things is that this function (via the types) guarantees that the output Vect has the same size as the input Vect.

Now, how to define a Functor instance so that we can use the plus3 function defined earlier ? Functor only deals with a type constructor which has only one parameter, and Vect has two parameters. To solve this issue, we will use the simplified syntax for type lambdas.

given vectFunctor[S <: Int] as Functor[ [X] =>> Vect[X, S] ] {
    def [A, B] (x: Vect[A, S]) map (f: A => B): Vect[B, S] = 
        Vect.map(x)(f)
}

The syntax is much clearer than with vanilla Scala 2 (the kind-projector plugin helped in this area), yet it still needs some explanations. Basically, we are building a parametrized given, which is the equivalent of Scala 2 implicit def of some sorts... this given is parametrized on S and state that we can build instances for any type X leading to a Vect[X, S]. Then, we just write the implementation by using the already defined map function.

This leads us to using it (with some verbosity):

val v = 4 :: 3 :: 2 :: Vect(2)
println(plus3[[X] =>> Vect[X, 4]](vect))
// Outputs: Cons(7,Cons(6,Cons(5,Cons(5,Empty)))) 

What's next ?

This is the end of this article. We still have plenty of things to try to solve our case:

• Make plus3[[X] =>> Vect[X, 4]](vect) to not force hardcoding the 4 type
• Fold a Vect
• ...

But so far, we saw that just as is, Dotty allows to do advanced stuff. Before the follow-up article, you can checkout the code written in this article on github.