Puzzled by type inference and polymorphic methods passed as functions


#1

Hi everyone,

Here is some code I’ve been looking at:

import cats.effect.{IO, Sync}

object test2 extends App {
  def doubleF[F[_] : Sync](t: Int): F[Int] = implicitly[Sync[F]].delay {
     t * 2
  }

  def stream[F[_] : Sync]: Seq[F[Int]] = {
    // Iterator.iterate(0)(_ + 1).take(5).toSeq.map(doubleF) // DOES NOT COMPILE
    Iterator.iterate(0)(_ + 1).take(5).toSeq.map(doubleF[F]) // Must include type paramter [F]
  }

  def double[F[_] : Sync](t: Int): F[Int] = {
    doubleF(t) // Works without needing the type parameter?
  }

  println(double[IO](10).unsafeRunSync())

  for (s <- stream[IO]) {
    println(s.unsafeRunSync())
  }
}

In the stream method, Iterator.iterate(0)(_ + 1).take(5).toSeq.map(doubleF) fails with a compiler error

Error:(13, 50) could not find implicit value for evidence parameter of type cats.effect.Sync[F]
    Iterator.iterate(0)(_ + 1).take(5).toSeq.map(doubleF) // Must include type paramter [F]
Error:(13, 50) not enough arguments for method doubleF: (implicit evidence$1: cats.effect.Sync[F])F[Int].
Unspecified value parameter evidence$1.
    Iterator.iterate(0)(_ + 1).take(5).toSeq.map(doubleF) // Must include type paramter [F]

If I ascribe the type parameter F as in Iterator.iterate(0)(_ + 1).take(5).toSeq.map(doubleF[F]) everything works fine however.

Could someone clarify what’s going on and why the compiler can’t supply the implicit F in this case?

I’ve made a Scala fiddle with the example here: https://scalafiddle.io/sf/kXKtOTJ/3


#2

My guess is that in this case

  def double[F[_] : Sync](t: Int): F[Int] = {
    doubleF(t) // Works without needing the type parameter?
  }

you’re invoking doubelF in tail position, i.e. return value from doubleF is a return value of double. Scala compiler can then deduce types backwards - from returned value type instead of parameters type.

OTOH in this case:

  def stream[F[_] : Sync]: Seq[F[Int]] = {
    // Iterator.iterate(0)(_ + 1).take(5).toSeq.map(doubleF) // DOES NOT COMPILE
    Iterator.iterate(0)(_ + 1).take(5).toSeq.map(doubleF[F]) // Must include type paramter [F]
  }

call to doubleF is not in a tail position so Scala compiler does not take type of returned value from stream (which is Seq[F[Int]]) into consideration when picking F passed to doubleF.

Also I think that expecting that Scala compiler will deduce a concrete type just because there is only one implicit value in scope that satisfies type bounds is wrong. I think it always works in the other direction - first types are deduced then implicits are searched (I may be wrong here, feel free to correct me).


#3

This compiles:

object test2 {
  def doubleF[F[_]: Sync](t: Int): F[Int] = implicitly[Sync[F]].delay {
    t * 2
  }

  def stream[F[_]: Sync]: List[F[Int]] = List(1).map(t => doubleF(t)) 
  //def stream[F[_]: Sync]: List[F[Int]] = List(1).map(doubleF) //this doesn't compile 

}

The problem must be with the eta expansion of doubleF. Taking the spec along, when we have s.map(doubleF), we have 6.26.2 (https://www.scala-lang.org/files/archive/spec/2.12/06-expressions.html#eta-expansion)

Eta Expansion
Otherwise, if the method is not a constructor, and the expected type pt is a function type (Ts′)⇒T′, eta-expansion is performed on the expression e.

What I think is happening is that the best we can expect in map is Int => F[Int], but doubleF needs an implicit Sync[F] before it can be eta expanded, where F still is a type parameter of doubleF (rather than the F it’s fixed to in the stream method.

The error message becomes clearer with

object test2 {
  def doubleF[NotF[_]: Sync](t: Int): NotF[Int] = implicitly[Sync[NotF]].delay {
    t * 2
  }

  def stream[F[_]: Sync]: List[F[Int]] = {
    val s: List[Int] = List(1)
    s.map(doubleF)
  }

}

which gives could not find implicit value for evidence parameter of type cats.effect.Sync[NotF] showing which F it is that it’s missing a Sync instance for: an unconstrained type parameter.

I’m not sure where the bug is here, whether it’s an inference bug, or an error message bug - or maybe not a bug. Inference is notoriously under-specced.

Looking for an implict for an unconstrained type parameter sounds like something that always has to fail, no? If so, maybe that should be the error message.

pinging @hrhino who seems to like this stuff.


#4

Actually that’s not always true.

scala> trait Foo[T]
defined trait Foo

scala> implicit def fooInt = new Foo[Int]{}
fooInt: Foo[Int]

scala> def foo[T: Foo]: T = null.asInstanceOf[T]
foo: [T](implicit evidence$1: Foo[T])T

scala> foo
res4: Int = 0

#6

So what’s happening there is that T gets inferred to be Int because the only implicit Foo in scope is a Foo[Int]?

That’s the darndest thing. Is that intended? Are there good applications of that?


#7

Not a clue… The fact that it only works when T doesn’t have a lower bound (i.e. it’s Nothing) suggests that this might be some funny side effect of how Nothing is used as a kind of flag during type inference. However it does still seem to work in dotty, which I suspect handles Nothing a bit better.

I don’t know about good, but you can use it to have some kind of “default type arguments”.

scala> :pa
// Entering paste mode (ctrl-D to finish)

sealed trait Infer[F[_]]
trait LowPriority {
  implicit def inferDefault[F[_]]: Infer[F] = new Infer[F] {}
}
object Infer extends LowPriority {
  type Id[A] = A
  implicit def inferId: Infer[Id] = new Infer[Id] {}
}

abstract class FooAbstraction[F[_]: Infer] { def foo: F[Int] }

// Exiting paste mode, now interpreting.

scala> class FooImpl extends FooAbstraction { def foo = 42 }
defined class FooImpl

scala> class FooListImpl extends FooAbstraction[List] { def foo = List.range(0, 42) }
defined class FooListImpl

#8

Yes: https://milessabin.com/blog/2011/07/16/fundeps-in-scala/


#9

So what’s happening there is that T gets inferred to be Int because the only implicit Foo in scope is a Foo[Int]? That’s the darndest thing. Is that intended? Are there good applications of that?

Isn’t this mechanism the entire basis of the current Scala collections library? All of the methods .map, .flatMap, etc. all have their return type determined by the types of the matching CanBuildFroms in the implicit scope (e.g. in companion objects).


#10

Neat, thanks!