type inference fails in a generic scala function

Question

consider a simple function that operates on collections distinctBy, which, like distinct remove "duplicates" (which are not necessary actual duplicates):

import scala.collection.TraversableLike
import scala.collection.generic.CanBuildFrom
import scala.collection.mutable.{Set=>MSet}

def distinctBy[T,R,Coll]
  (xs: Coll)
  (f: T => R)
  (implicit ev: Coll <:< TraversableLike[T,Coll], 
   cbf: CanBuildFrom[Coll,T,Coll]): Coll = {

  val builder = cbf(xs)
  builder.sizeHint(xs.size)
  val seen = MSet.empty[R]

  xs.foreach { elem =>
    if(!seen(f(elem))){
      builder += elem
    }
  }
  builder.result()
}

now consider a class to use it on:

case class X(i: Int, j: Int)

using this function naively fails:

scala> distinctBy(Vector(X(1,2),X(3,2),X(1,1),X(2,2)))(_.i)
<console>:14: error: missing parameter type for expanded function ((x$1) => x$1.i)
              distinctBy(Vector(X(1,2),X(3,2),X(1,1),X(2,2)))(_.i)
                                                          ^
<console>:14: error: Cannot construct a collection of type scala.collection.immutable.Vector[X] with elements of type Any based on a collection of type scala.collection.immutable.Vector[X].
              distinctBy(Vector(X(1,2),X(3,2),X(1,1),X(2,2)))(_.i)
                                                             ^

but if I help the type inferencer, this works:

scala> distinctBy(Vector(X(1,2),X(3,2),X(1,1),X(2,2)))((x:X) => x.i)
res1: scala.collection.immutable.Vector[X] = Vector(X(1,2), X(3,2), X(1,1), X(2,2))

scala> distinctBy[X,Int,Vector[X]](Vector(X(1,2),X(3,2),X(1,1),X(2,2)))(_.i)
res2: scala.collection.immutable.Vector[X] = Vector(X(1,2), X(3,2), X(1,1), X(2,2))

to my best understanding, since the function is given in a second argument list, the type inferencer should have picked up that it's a function from X to something. and since X has a member i of type Int, all should have been OK with the first try. so, what am I missing here?

vvg · Accepted Answer · 2015-10-28T12:20:26.950

2

This simplified version works fine for me:

object A {
  def f1[T, R](l: List[T])(f: T=>R) = None

  case class X(i: Int, j: Int)

  f1(List(X(1,1),X(2,1)))(_.i)
}

As you can see collection in first parameter list has T type that allows scala inference type in second arguments list.

So you need build somehow dependencies between Col and T in your example. Not sure if third implicits parameters list helps here.

UPD. Looks weird but seems it works:

object A {
  def f1[T, R, Col[Z]](l: Col[T])(f: T => R) = None

  case class X(i: Int, j: Int)

  f1(List(X(1,1),X(2,1)))(_.i)
}

UPD2. Rewritten sample from question.

  import scala.collection.TraversableLike
  import scala.collection.generic.CanBuildFrom
  import scala.collection.mutable.{Set=>MSet}

  def distinctBy[T,R,Coll[Z]]
  (xs: Coll[T])
  (f: T => R)
  (implicit ev: Coll[T] <:< TraversableLike[T,Coll[T]],
   cbf: CanBuildFrom[Coll[T],T,Coll[T]]): Coll[T] = {

    val builder = cbf(xs)
    builder.sizeHint(xs.size)
    val seen = MSet.empty[R]

    xs.foreach { elem =>
      if(!seen(f(elem))){
        builder += elem
        seen.add(f(elem))
      }
    }
    builder.result()
  }

  case class X(i: Int, j: Int)

  distinctBy(Vector(X(1,2),X(1,2),X(3,2),X(1,1),X(2,2)))(_.i)
  distinctBy(Map("1" -> X(1,2), "2" -> X(1,2), "3" -> X(3,2)))(_._2.i)

edited Oct 28 '15 at 12:20

answered Oct 28 '15 at 11:35

vvg

6,325
19
36

yes' but it would work only on collections that receives exactly one type parameter. i.e. collections like `IntList extends List[Int]`,`Map[K,V]`, cannot be used with such a function. it won't compile. – gilad hoch Oct 28 '15 at 11:54
@gilad hoch , i've updated post... that probably not what you've expected .. as T takes different types but not X all the time. – vvg Oct 28 '15 at 12:02
I can't see how this would work. Could you try implementing `distinctBy` and show how to use it with the failed attempt from my question? – gilad hoch Oct 28 '15 at 12:08
done. it works as expected with both maps and lists. also I've fixed minor bug in your logic of duplications check. – vvg Oct 28 '15 at 12:21
yup, this works :) but I still don't understand what you did there. you're not using type `Z` anywhere, so I guess it could have been replaced by `_`, and besides, why is it needed in the first place? I tried testing it with : `class XTraversable extends Traversable[X] {def foreach[U](f: X => U) = {for {i <- 1 to 5; j <- 1 to 5}{f(X(i,j))}}}; distinctBy(new XTraversable)(_.i)` and it worked, so you got it right, I just don't understand it. could you provide an explanation or a refernce I could read to understand it? thanks! – gilad hoch Oct 28 '15 at 12:35
It's called higher kinded types in Scala. Please check: http://stackoverflow.com/questions/6246719/what-is-a-higher-kinded-type-in-scala – vvg Oct 28 '15 at 12:44
I'm aware of higher kinded types, just don't see how it comes to the help in my case. anyway, thanks :) – gilad hoch Oct 28 '15 at 12:51

type inference fails in a generic scala function

1 Answers1