Is it possible to write down a dependent function type in Scala?

Question

Given

trait Foo {
  type Bar
}

is there a legal way to write something like f: (x: Foo) => x.Bar, so that the return type of the function depends on the argument? An example of use would be

def compareOutput(x1: Foo, x2: Foo)(f: (x: Foo) => x.Bar /* illegal */)(comparer: (x1.Bar, x2.Bar) => Boolean) = {
  val y1 = f(x1)
  val y2 = f(x2)
  comparer(y1, y2)
}

Answer 1

Scala does not have polymorphic functions as for example Haskell does. A Function type is always concrete. Only methods can be polymorphic. That does unfortunately mean, that your hypothetical type (x: Foo) => x.Bar is not expressible in Scala.

This becomes obvious when converting generic methods to functions: all type information is lost:

scala> def foo[Bar](x: Bar): Bar = ???
foo: [Bar](x: Bar)Bar

scala> foo _
res1: Nothing => Nothing = <function1>

You might have also noticed that scala does fail to convert methods with dependent types to functions. That is because it is impossible to satisfy your hypothetical type:

scala> def foo(x: Foo): x.Bar = ???
foo: (x: Foo)x.Bar

scala> foo _
<console>:10 error: method with dependent type (x: Foo)x.Bar cannot be converted 
                    to function value.

Also see this and this questions.

---

There are however several solutions to your Problem. One would be to encapsulate your dependently typed method in a helper trait:

trait FooFunc {
  def apply(x: Foo): x.Bar
}

def compareOutput(x1: Foo, x2: Foo)(f: FooFunc)(comparer: ...) = {
  val y1 = f(x1)
  val y2 = f(x2)
  comparer(y1,y2)
}

You could then create instances of FooFunc which you can pass into your compareOutput method.

Answer 2

Scala 3 is expected to be released this year (2020). It will have (already has, in fact) dependent function types, described here in the "Dotty" documentation:

https://dotty.epfl.ch/docs/reference/new-types/dependent-function-types.html