pre-sip.md

Table of Contents

1. Proposal
   1. Motivation
      1. Examples
   2. Summary
   3. Implementation
   4. Acknowledgements

Proposal

Motivation

Type aliases are heavily used in functional libraries such as cats, fs2 and ZIO, to provide friendlier type signatures over the more complex encodings which are used within the library itself.

This allows the libraries to hide some of the complexity to newcomers who may never need it, but still allow the library to be general enough to cater to the more complex use-cases.

A pattern which has emerged is to have a companion object as an entry point, which addresses the problem of discoverability, but the aliases which are defined are not preserved in function composition, which leads to "leakage" of the complexity which authors are trying to hide in the first place.

This proposal aims to address the issue.

Examples

Consider the following snippet of code, which uses the pattern described. Reader is the simplified type alias with the companion object.

    type Id[A] = A

    case class ReaderT[F[_], A, B](run: A => F[B]) {
      def flatMap[BB](f: B => ReaderT[F, A, BB]): ReaderT[F, B, BB] = ???
    }

    type Reader[A, B] = ReaderT[Id, A, B]

    object Reader {
      def apply[A, B](f: A => B): Reader[A, B] = ReaderT(f)
    }

    val provided: ReaderT[Id, String, String] = ???
    val problem = Reader[Int, String](_.toString).flatMap(_ => provided)

If at some other point in time a newcomer has the following snippet of code,

    val problematic: Reader[String, String] = ???
    Reader[Int, String](_.toString).flatMap(_ => problematic)

we get the following error message:

    [error] -- [E007] Type Mismatch Error: /home/user/helloworld/src/main/scala/Example.scala:19:51
    [error] 19 |val line = Reader[Int, String](_.toString).flatMap(_ => problematic)
    [error]    |                                                       ^^^^^^^
    [error]    |  Found:    (foo.problematic : foo.ReaderT[foo.Id, String, String])
    [error]    |  Required: foo.ReaderT[foo.Id, Int, String]

Ideally, the ReaderT[foo.Id, Int, String] should be replaced with Reader[Int, String].

This is even worse when we "create" aliases through composition. Consider the snippet below for a profunctor lens encoding.

    trait Profunctor[F[_, _]]
    trait Cartesian[F[_, _]] extends Profunctor[F]
    trait Cocartesian[F[_, _]] extends Profunctor[F]

    case class Optic[-C[_[_, _]], -S, +T, +A, -B]() {
      def <<<[U, V, C1[F[_, _]] <: C[F]](other: Optic[C1, U, V, S, T]): Optic[C1, U, V, A, B] = ???
    }

    type Lens[-S, +T, +A, -B] = Optic[Cartesian, S, T, A, B]
    type Prism[-S, +T, +A, -B] = Optic[Cocartesian, S, T, A, B]
    type Optional[-S, +T, +A, -B] = Optic[[F[_, _]] =>> Cartesian[F] & Cocartesian[F], S, T, A, B]

    type MLens[S, A] = Optic[Cartesian, S, S, A, A]
    type MPrism[S, A] = Optic[Cocartesian, S, S, A, A]
    type MOptional[S, A] = Optic[[F[_, _]] =>> Cartesian[F] & Cocartesian[F], S, S, A, A]

The following snippet of user code,

    val lens: MLens[String, String] = ???
    val prism: MPrism[String, Int] = ???
    val what: MPrism[String, Int] = prism <<< lens

would produce the error message:

    [error] -- [E007] Type Mismatch Error: /home/user/helloworld/src/main/scala/Help.scala:40:42
    [error] 40 |val what: MPrism[String, Int] = prism <<< lens
    [error]    |                                          ^^^^
    [error]    |    Found:    (foo.lens : foo.MLens[String, String])
    [error]    |    Required: foo.Optic[foo.Cocartesian, String, String, String, String]

Summary

We propose that the compiler should alias applied types to the most precise type alias before outputting error messages to the user.

In would be impractical to search everywhere in the context, so we limit the scope to be searched to be on the prefix of the type.

The most precise type would be one which had the least cardinality. The cardinality referred to here, is the cardinality of types. For the purposes of discussion, we can define a partial order on the cardinality of types where an unrestricted type parameter is the terminal object, and for all refined types A and B, A > B if and only if the lower bound of A is a supertype of the lower bound of B and the upper bound of A is a subtype of the lower bound of B.

We can summarize most precise as type alias which has the least number of type parameters and the most narrowed bounds.

We are unsure if this should be extended to all refined types, or simply type applications, since the pattern described has only appeared when using type applications.

Implementation

A rudimentary implementation can be found on the branch here. The examples can be run using dotc tests/neg/reader-realias.scala and dotc tests/neg/optic-realias.scala.

An example of the error messages produced is shown below.

-- [E007] Type Mismatch Error: tests/neg/reader-realias.scala:14:59 ------------
14 |val problem = Reader[Int, String](_.toString).flatMap(_ => provided)
   |                                                           ^^^^^^^^
   |                      Found:    (provided : type Reader[String, String])
   |                      Required: type Reader[Int, BB]
   |
   |                      where:    BB is a type variable
1 error found

-- [E007] Type Mismatch Error: tests/neg/optic-realias.scala:22:42 -------------
22 |val what: MPrism[String, Int] = prism <<< lens
   |                                          ^^^^
   |                        Found:    (foo.lens : foo.MLens[String, String])
   |                        Required: type MPrism[String, String]
1 error found

Acknowledgements

Many thanks to the creators and contributors of the libraries for the examples. Special thanks to Julien Truffaut, Zainab Ali, Adam Fraser and John De Goes for early feedback of this proposal.