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.