Type inference on Set failing?

I agree it would be nice to infer "the only possible" type, even when calls are chained, but there are technical limitations You can think of inference as a bread-first sweep over the expression, collecting constraints (which arise from subtype bounds and required implicit arguments) on type variables, followed by solving those constraints. This approach allows, e.g. , implicits to guide type inference.In your example, even though there is a single solution if you only look at the xs. ToSet subexpression, later chained calls could introduce constraints that make the system unsatisfiable.

The downside of leaving the type variables unsolved is that type inference for closures requires the target type to be known, and will thus fail (it needs something concrete to go on -- the required type of the closure and the type of its argument types must not both be unknown) Now, when delaying solving the constraints makes inference fail, we could backtrack, solve all the type variables, and retry, but this is tricky to implement (and probably quite inefficient).

I agree it would be nice to infer "the only possible" type, even when calls are chained, but there are technical limitations. You can think of inference as a bread-first sweep over the expression, collecting constraints (which arise from subtype bounds and required implicit arguments) on type variables, followed by solving those constraints. This approach allows, e.g. , implicits to guide type inference.

In your example, even though there is a single solution if you only look at the xs. ToSet subexpression, later chained calls could introduce constraints that make the system unsatisfiable. The downside of leaving the type variables unsolved is that type inference for closures requires the target type to be known, and will thus fail (it needs something concrete to go on -- the required type of the closure and the type of its argument types must not both be unknown).

Now, when delaying solving the constraints makes inference fail, we could backtrack, solve all the type variables, and retry, but this is tricky to implement (and probably quite inefficient).

2 I forgot to add: you can see the type inference in action with the -Ytyper-debug command line option. I highly recommend reducing your example to the bare minimum first, or you'll quickly get lost in the heaps of debug output. We are working on a tool that visualises this information.

– Adriaan Moors May 25 at 12:07 So...this is just an infelicity in the implementation that may go away at some point? I still don't understand what constraints are being added that makes everything unsatisfiable, particularly when the two-step example works. (I didn't get anything concrete from the other two answers, and when pressed further the answerers also say in the comments that they don't fully understand what's going on under the hood.) – Yang Jul 14 at 2:48.

A: Perhaps the fault is in yourself, not in toSet. Q: But why doesn't this compile? List(1).toSet.

Map(x => ...) A: The Scala compiler is unable to infer that x is an Int. Q: What, is it stupid? A: Well, ListA.

ToSet doesn't return an immutable.SetA. It returns an immutable. SetB for some unknown B >: A.

Q: How was I supposed to know that? A: From the Scaladoc. Q: But why is toSet defined that way?

A: You might be assuming immutable. Set is covariant, but it isn't.It's invariant. And the return type of toSet is in covariant position, so the return type can't be allowed to be invariant.

Q: What do you mean, "covariant position"? A: Let me Wikipedia that for you: http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science) . See also chapter 19 of Odersky, Venners & Spoon.

Q: I understand now. But why is immutable. Set invariant?

A: Let me Stack Overflow that for you: Why is Scala's immutable Set not covariant in its type? Q: I surrender. How do I fix my original code?

A: This works: List(1).toSetInt. Map(x => ...). So does this: List(1).toSet.

Map((x: Int) => ...) (with apologies to Friedman & Felleisen. Thx to paulp & ijuma for assistance) (reproduced from http://scalatastic.blogspot.com/2010/02/why-doesnt-toset-do-what-i-want.html).

A: I know your answer is supposed to sound smart and ironic... - Q: Yeah! You have SO seen through me! - A: I know.

But to me, it's just too arrogant. - Q: Oh, you are right. Now that you say that, I actually AM arrogant.

- A: And your answer makes the original poster look stupid by putting stupid words in his mouth. - Q: You're right. That was actually really stupid of me.

- A: We COULD infer almost everything on StackOverflow from some documentation. Would you therefore consider StackOverflow useless? - A: No.

Maybe sometimes asking is better. – Madoc Apr 4 at 22:36 1 I'll cancel my career change. I'm not cut out to be a comedian after all.

– Seth Tisue Apr 4 at 22:40 1 @Seth Tisue This is great but the Scala compiler IS able to infer that x is an Int. As we can see: scala> xs. ToSet res42: scala.collection.immutable.

SetInt = Set(1, 2, 3) It creates a Set of Int. Why can't it infer it in the first case? – Adrian Apr 4 at 23:36 1 @Adrian: I don't know.

My answer is incomplete. I think it has to do with the details of how type inference proceeds.In some ambiguous situations it gives up and refuses to infer a type; in others it goes ahead and just picks the most specific applicable type (here, Int). In general, it seems much more reluctant to infer parameter types (which we're asking it do in the 1-step example) then result types (which is all the 2-step example requires).

If anyone has any further insight into, this I'd love to hear it (especially if it involves quoting chapter and verse from the Scala spec). – Seth Tisue Apr 4 at 23:52 1 Actually, toSet is being called on a List, which is co-variant. However, Traversable is not, and that's where toSet is defined.

– Daniel C. Sobral Apr 47 at 2:05.

The type inference does not work properly as the signature of List#toSet is def toSetB >: A => scala.collection.immutable. SetB and the compiler would need to infer the types in two places in your call. An alternative to annotating the parameter in your function would be to invoke toSet with an explicit type argument: xs.

ToSetInt map (_*2) UPDATE: Regarding your question why the compiler can infer it in two steps, let's just look at what happens when you type the lines one by one: scala> val xs = List(1,2,3) xs: ListInt = List(1, 2, 3) scala> val ys = xs. ToSet ys: scala.collection.immutable. SetInt = Set(1, 2, 3) Here the compiler will infer the most specific type for ys which is SetInt in this case.

This type is known now, so the type of the function passed to map can be inferred. If you filled in all possible type parameters in your example the call would be written as: xs.toSetInt. MapInt,SetInt(_*2) where the second type parameter is used to specify the type of the returned collection (for details look at how Scala collections are implemented).

This means I even underestimated the number of types the compiler has to infer. In this case it may seem easy to infer Int but there are cases where it is not (given the other features of Scala like implicit conversions, singleton types, traits as mixins etc. ). I don't say it cannot be done - it's just that the Scala compiler does not do it.

1 Thanks for the solution. I'm still not clear why the compiler cannot infer it in one step, since it can infer the types in 2 steps, as shown in the REPL code. – Adrian Apr 4 at 22:29 Isn't type inference supposed to work "step by step"?

Even Java has this kind of "type inference" on chained expressions. – Adrian Apr 4 at 23:57 Thanks! I saw that question before, and was completely at loss as to what was the reason for the problem.

– Daniel C. Sobral Apr 5 at 1:53 1 @Adrian normally it is but once you add polymorphism to your type system, type inference becomes undecidable in some cases. My guess is that the Scala compiler is somewhat conservative in situations where such problems can occur.In Java you cannot even write an expression like that without either specifying all type parameters or using raw types - at least the function argument would need to be type annotated and in that case Scala can also infer the types correctly.

– Moritz Apr 5 at 8:12.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.