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)
}

See for example [how Miles Sabin uses dependent method types in Shapeless](https://github.com/milessabin/shapeless/blob/master/core/src/main/scala/shapeless/syntax/hlists.scala). — Travis Brown, Apr 04 '14 at 12:57
I don't think that is relevant. He wants to be able to define a function type (as opposed to just defining a method) where the return type depends on the argument value. I belive this is currently impossible. Even you manage to define a type that matches OP's intent, I don't think you would be able to pass a method as the argument `f` because eta-expansion does not support dependent method types. See https://issues.scala-lang.org/browse/SI-4751. This would force to define those "dependeant functions" in a rather awkward manner, such as extending a custom trait & implementing its `apply` method — Régis Jean-Gilles, Apr 04 '14 at 13:10
@RégisJean-Gilles: You're right—I may have been reading too quickly. What you describe could be done with Shapeless's polymorphic function values, but not vanilla Scala functions. — Travis Brown, Apr 04 '14 at 13:12

score 8 · Accepted Answer · edited May 23 '17 at 12:01

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.

score 2 · Answer 2 · answered Aug 25 '20 at 01:25

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

answered Aug 25 '20 at 01:25

AmigoNico

6,652
1
35
45

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

2 Answers2