Support dependent function types #4751

scabug · 2011-07-01T08:14:59Z

Sample REPL session with -Ydependent-method-types. The following with a dependent argument type fails,

scala> trait Dep {
     |    type T                                                                                                                                                                                       
     |  }                                                                                                                                                                                              
defined trait Dep

scala> def m(d : Dep)(t : d.T) = t
m: (d: Dep)(t: d.T)d.T

scala> val f = m _
<console>:12: error: method with dependent type (d: Dep)(t: d.T)d.T cannot be converted to function value
       val f = m _

whereas with a type projection (ie. changing d.T to Dep#T) we succeed,

scala> def m(d : Dep)(t : Dep#T) = t
m: (d: Dep)(t: Dep#T)Dep#T

scala> val f = m _
f: Dep => Dep#T => Dep#T = <function1>

Having both these constructs supported equally would be highly desirable for the usability of dependent methods in Scala.

A more complete example which illustrates the usefulness of dependent function types,

implicit def m[D <: Dep](d : D)(implicit t : d.T) = t

def n[D <: Dep](d : D)(implicit f : D => d.T) = f(d)

val dep = new Dep { type T = String }
implicit val s : String = "foo"

val r : String = n(dep)

Here we would like m to be considered as a candidate for the implicit f in n. It isn't because eta expansion would generate a dependent function type corresponding to m.

scabug · 2011-07-01T08:14:59Z

Imported From: https://issues.scala-lang.org/browse/SI-4751?orig=1
Reporter: @milessabin

scabug · 2012-06-17T23:59:36Z

Rich Oliver (rich oliver) said:
I just came up against this problem in my project. I can get around it by calling a method rather than a function, but it does require every user to repeat code. A more general issue is the inability to extend an inner (path dependant) class without the path, ie outside of the outer class. If that were solved then this feature would be less useful.

scabug · 2012-07-12T02:10:04Z

Denis Petrov (denis) said:
May be related: #6065

scabug · 2013-01-15T16:13:53Z

@retronym said:
I guess you would need to generalize FunctionN to something like:

scala> trait DepFunction1[-A <: AnyRef, +Return[_]] { def apply(a: A) : Return[a.type] }
warning: there were 1 feature warnings; re-run with -feature for details
defined trait DepFunction1

scala> trait NewFunction1[-A <: AnyRef, +R] extends DepFunction1[A, ({type l[_] = R})#l]
defined trait NewFunction1

scala> object stringId extends DepFunction1[String, ({type Id[x] = x})#Id] { def apply(s: String): s.type = s }
defined object stringId

Where Return is a type level function that accepts the singleton types of the parameters and uses these to compute the result type. Sounds pretty hairy.

scabug · 2013-01-15T19:00:20Z

@xeno-by said:
http://groups.google.com/group/scala-internals/browse_thread/thread/85241ae6ea51b315

scabug · 2013-01-18T16:27:43Z

@Blaisorblade said (edited on Jan 18, 2013 4:44:43 PM UTC):
Jason Zaugg, your example is almost right, but not quite.

It takes a small variant for DepFunction1 to express the type of:

def f(a: T1)(b: a.MemberT2): b.MemberT3

I'll parametrize over T1 below, so f will be written as:

def f[T1 <: {type MemberT2 <: {type MemberT3}}](a: T1)(b: a.MemberT2): b.MemberT3 = ???

But I assume a concrete type with the right members would also work. I was just too bored to make things that simple :-).

The problem is that for the above case, Return cannot be defined over all types, only over subtypes of T1 with the right type member. So with your DepFunction1, I get this kind error:

scala> def g[T1 <: {type MemberT2 <: {type MemberT3}}]: DepFunction1[T1, ({type Ret[x <: T1] = DepFunction1[x#MemberT2, ({type Ret[y <: x#MemberT2] = y#MemberT3})#Ret]})#Ret] = ??? 
<console>:8: error: kinds of the type arguments (T1,[x <: T1]DepFunction1[x#MemberT2,[y <: x#MemberT2]y#MemberT3]) do not conform to the expected kinds of the type parameters (type A,type Return) in trait DepFunction1.
[x <: T1]DepFunction1[x#MemberT2,[y <: x#MemberT2]y#MemberT3]'s type parameters do not match type Return's expected parameters:
type x's bounds <: T1 are stricter than type _'s declared bounds >: Nothing <: Any
       def g[T1 <: {type MemberT2 <: {type MemberT3}}]: DepFunction1[T1, ({type Ret[x <: T1] = DepFunction1[x#MemberT2, ({type Ret[y <: x#MemberT2] = y#MemberT3})#Ret]})#Ret] = ??? 
                                                        ^

scabug · 2013-01-18T16:32:05Z

@Blaisorblade said:
In this section, I show how to express the type of f.

//Variant: Note that Return must only accept subtypes of A
trait DepFunction1[-A <: AnyRef, +Return[_ <: A]] { def apply(a: A) : Return[a.type] }
//Your examples still work - the kind needn't match:
object stringId extends DepFunction1[String, ({type Id[x] = x})#Id] { def apply(s: String): s.type = s }
trait Function1[-A <: AnyRef, +R] extends DepFunction1[A, ({type l[_] = R})#l]
//Now we can write:
def g[T1 <: {type MemberT2 <: {type MemberT3}}]: DepFunction1[T1, ({type Ret[x <: T1] = DepFunction1[x#MemberT2, ({type Ret[y <: x#MemberT2] = y#MemberT3})#Ret]})#Ret] = ???

That worked well! But we didn't yet eta-expand f, only represented the interface for that. There, I get an error I don't get (no pun intended):

scala> def g[T1 <: {type MemberT2 <: {type MemberT3}}]: DepFunction1[T1, ({type Ret[x <: T1] = DepFunction1[x#MemberT2, ({type Ret[y <: x#MemberT2] = y#MemberT3})#Ret]})#Ret] =
     |   new DepFunction1[T1, ({type Ret[x <: T1] = DepFunction1[x#MemberT2, ({type Ret[y <: x#MemberT2] = y#MemberT3})#Ret]})#Ret] {
     |     def apply(a: T1) = new DepFunction1[a.MemberT2, ({type Ret[y <: a.MemberT2] = y#MemberT3})#Ret] {
     |       def apply(b: a.MemberT2): b.MemberT3 = f(a)(b) //": b.MemberT3" is required, else we get more errors.
     |     }
     |   }
<console>:10: error: type mismatch;
 found   : DepFunction1(in object $iw)[a.MemberT2,[y <: a.MemberT2]y#MemberT3]
 required: DepFunction1(in object $iw)[a.MemberT2,[y <: a.MemberT2]y#MemberT3]
           def apply(a: T1) = new DepFunction1[a.MemberT2, ({type Ret[y <: a.MemberT2] = y#MemberT3})#Ret] {
                              ^

scabug · 2013-01-18T16:32:22Z

@retronym said:
So I was at least right about the "hairy" part :)

scabug · 2013-01-18T16:43:39Z

@Blaisorblade said:
It's just a type inference bug. If you write down as return type exactly what Scalac inferred, everything works. If Scalac infers the type itself, he doesn't like what he did, although it looks the same as the expected type. Misteries of Scala programming.

Minimized:

scala> def g[T1 <: {type MemberT2}]: DepFunction1[T1, ({type Ret[x <: T1] = x#MemberT2})#Ret] =
     |   new DepFunction1[T1, ({type Ret[x <: T1] = x#MemberT2})#Ret] {
     |     def apply(a: T1) = f2(a)
     |   }
<console>:11: error: type mismatch;
 found   : a.MemberT2
 required: a.MemberT2
           def apply(a: T1) = f2(a)
                                ^

Workarounded:

scala> def g[T1 <: {type MemberT2}]: DepFunction1[T1, ({type Ret[x <: T1] = x#MemberT2})#Ret] =
     |   new DepFunction1[T1, ({type Ret[x <: T1] = x#MemberT2})#Ret] {
     |     def apply(a: T1): a.MemberT2 = f2(a)
     |   }
g: [T1 <: AnyRef{type MemberT2}]=> DepFunction1[T1,[x <: T1]x#MemberT2]

Note that I just added an explicit type annotation.
Backporting this to the original code, I get working code:

scala> def g[T1 <: {type MemberT2 <: {type MemberT3}}]: DepFunction1[T1, ({type Ret[x <: T1] = DepFunction1[x#MemberT2, ({type Ret[y <: x#MemberT2] = y#MemberT3})#Ret]})#Ret] =
     |   new DepFunction1[T1, ({type Ret[x <: T1] = DepFunction1[x#MemberT2, ({type Ret[y <: x#MemberT2] = y#MemberT3})#Ret]})#Ret] {
     |     def apply(a: T1): DepFunction1[a.MemberT2, ({type Ret[y <: a.MemberT2] = y#MemberT3})#Ret] =
     |       new DepFunction1[a.MemberT2, ({type Ret[y <: a.MemberT2] = y#MemberT3})#Ret] {
     |         def apply(b: a.MemberT2): b.MemberT3 = f(a)(b)
     |       }
     |     }
g: [T1 <: AnyRef{type MemberT2 <: AnyRef{type MemberT3}}]=> DepFunction1[T1,[x <: T1]DepFunction1[x#MemberT2,[y <: x#MemberT2]y#MemberT3]]

scabug · 2013-01-20T02:10:44Z

@Blaisorblade said:

So I was at least right about the "hairy" part.
Feel free to take a look at Agda's operator for function composition:

○ : {A : Set} {B : A -> Set} {C : (x : A) -> B x -> Set} →
(∀ {x} → (y : B x) → C x y) -> (g : (x : A) -> B x) -> (∀ x -> C x (g x))
(f ○ g) x = f (g x)

A : Set means that A is a type parameter, and arguments between {} are just Agda's implicits (which are deduced by unification) - some of that is what I'd like in Scala as well:
http://blaisorbladeprog.blogspot.de/2013/01/flexible-implicits-from-agda-for-scala.html

scabug · 2013-05-21T17:34:58Z

@milessabin said (edited on May 21, 2013 5:35:52 PM UTC):
Revisiting this now, it seems fairly straightforward to encode the motivating example (ie. the dependent implicit),

scala> trait Dep { type T }                                                                                              
defined trait Dep                                                                                                        
                                                                                                                         
scala> implicit def m[T0](d : Dep { type T = T0 })(implicit t : T0) = t
m: [T0](d: Dep{type T = T0})(implicit t: T0)T0                                                                           
                                                                                                                         
scala> def n[T0](d : Dep { type T = T0 })(implicit f : Dep { type T = T0} => T0) = f(d)                                  
n: [T0](d: Dep{type T = T0})(implicit f: Dep{type T = T0} => T0)T0                                                       
                                                                                                                         
scala> val dep = new Dep { type T = String }                                                                             
dep: Dep{type T = String} = $anon$1@4b6393b3                                                                             
                                                                                                                         
scala> implicit val s : String = "foo"                                                                                   
s: String = foo                                                                                                          
                                                                                                                         
scala> val r = n(dep)                                                                                                    
r: String = foo

This is simply trading the dependent type d.T for a refinement Dep { type T = T0 } and a use of the constraining type T0.

scabug · 2014-02-17T02:15:52Z

@Blaisorblade said:

If Scalac infers the type itself, he doesn't like what he did, although it looks the same as the expected type. Misteries of Scala programming.
I am seeing this again and again in 2.10.3. I'm hoping that the fix to "substitution broken for dependent types", #7753, might help there.

scabug · 2014-04-18T12:46:19Z

@retronym said:
Another request from #8515

Details
Type:Bug Bug
Status:CLOSED
Priority:Major Major
Resolution: Duplicate
Affects Version/s:
Scala 2.10.3, Scala 2.10.4
Fix Version/s: None
Component/s:
Type Checker, Type Inference
Labels:
existential type-inference
Description
Welcome to Scala version 2.10.3 (Java HotSpot(TM) 64-Bit Server VM, Java 1.7.0_45).
Type in expressions to have them evaluated.
Type :help for more information.
 
scala> class C { trait T }
defined class C
 
scala> val c = new C
c: C = C@1130ed80
 
scala> val t1: c.T = (new { def apply(c: C) = new c.T {} })(c)
t1: c.T = $anon$2$$anon$1@23309add
 
scala> val t2: c.T = ({c: C => new c.T {} })(c)
<console>:9: error: type mismatch;
 found   : $anon where type $anon <: c.T
 required: c.T
       val t2: c.T = ({c: C => new c.T {} })(c)
                                            ^
 
scala> val f1: { def apply(c: C): c.T } = {c: C => new c.T {} }
<console>:9: error: type mismatch;
 found   : C => $anon forSome { type $anon <: c.T; val c: C }
 required: AnyRef{def apply(c: C): c.T}
       val f1: { def apply(c: C): c.T } = {c: C => new c.T {} }
                                                ^
The function literal is inferred to existential type
C => $anon forSome { type $anon <: c.T; val c: C }
, which looks complex, but it is no more special than simple C => C#T.
Could you infer the function literal to
(C => C#T) with { def apply(c: C): c.T }

scabug · 2014-04-18T13:35:09Z

@Blaisorblade said:
This part seems #7051 in action again:

scala> val t2: c.T = ({c: C => new c.T {} })(c)
<console>:9: error: type mismatch;
 found   : $anon where type $anon <: c.T
 required: c.T
       val t2: c.T = ({c: C => new c.T {} })(c)

Also improve test coverage by: - portraying the different possible translations of the intMonoid example - demonstrating issues with the scalac compiler's type inference mechanism

SethTisue · 2021-11-10T19:45:31Z

out of scope for Scala 2

(if someone would like to comment with links to information about where Scala 3 stands on this, please do)

scabug added enhancement quickfix typer depmet labels Apr 7, 2017

scabug added this to the Backlog milestone Apr 7, 2017

This was referenced Apr 7, 2017

error: method with dependent type (tre: c.Tree)c.Tree cannot be converted to function value #6065

Closed

Eta-expansion too conservative wrt dependent method type #7815

Closed

The existential type inferred from function literal is useless. #8515

Closed

hrhino removed the quickfix label Aug 1, 2017

scala deleted a comment from scabug Nov 10, 2021

SethTisue closed this as completed Nov 10, 2021

SethTisue removed this from the Backlog milestone Nov 10, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Support dependent function types #4751

Support dependent function types #4751

scabug commented Jul 1, 2011

scabug commented Jul 1, 2011

scabug commented Jun 17, 2012

scabug commented Jul 12, 2012

scabug commented Jan 15, 2013

scabug commented Jan 15, 2013

scabug commented Jan 18, 2013

scabug commented Jan 18, 2013

scabug commented Jan 18, 2013

scabug commented Jan 18, 2013

scabug commented Jan 20, 2013

scabug commented May 21, 2013

scabug commented Feb 17, 2014

scabug commented Apr 18, 2014

scabug commented Apr 18, 2014

SethTisue commented Nov 10, 2021 •

edited

Support dependent function types #4751

Support dependent function types #4751

Comments

scabug commented Jul 1, 2011

scabug commented Jul 1, 2011

scabug commented Jun 17, 2012

scabug commented Jul 12, 2012

scabug commented Jan 15, 2013

scabug commented Jan 15, 2013

scabug commented Jan 18, 2013

scabug commented Jan 18, 2013

scabug commented Jan 18, 2013

scabug commented Jan 18, 2013

scabug commented Jan 20, 2013

scabug commented May 21, 2013

scabug commented Feb 17, 2014

scabug commented Apr 18, 2014

scabug commented Apr 18, 2014

SethTisue commented Nov 10, 2021 • edited

SethTisue commented Nov 10, 2021 •

edited