Scala higher-kinded types: can't define a generic function that works on different collections

Question

I'm using Scala 2.10.2.

I need a function

def extractEither(m: M[(Key, Either[TLeft, TRight])])
: Either[TLeft, M[(Key, TRight)]]

where M can be Seq, List, Map or anything else and the return type would still be appropriate.

I'm using following for testing:

val map = Map(1 -> Left("foo"), 2 -> Right('bar), 3 -> Right('baz))

My current attempts are as follows:

Attempt #1

def extractEither[
  Key, TLeft, TRight, M[_] <: TraversableOnce[_]
]
(monad: M[(Key, Either[TLeft, TRight])])
(implicit cbf: CanBuildFrom[
M[(Key, Either[TLeft, TRight])],
  (Key, TRight),
  M[(Key, TRight)]
]): Either[TLeft, M[(Key, TRight)]] = {
  val builder = cbf(monad)
  builder.sizeHint(monad.size)
  (monad: GenTraversableOnce[_]).foreach { x =>
    val (key, either) = x.asInstanceOf[(Key, Either[TLeft, TRight])]
    either.fold(
      leftVal => return Left(leftVal),
      rightVal => builder += ((key, rightVal))
    )
  }
  Right(builder.result())
}

This fails with:

scala> extractEither(map)
<console>:20: error: no type parameters for method extractEither: (monad: M[(Key, Either[TLeft,TRight])])(implicit cbf: scala.collection.generic.CanBuildFrom[M[(Key, Either[TLeft,TRight])],(Key, TRight),M[(Key, TRight)]])Either[TLeft,M[(Key, TRight)]] exist so that it can be applied to arguments (scala.collection.immutable.Map[Int,Product with Serializable with scala.util.Either[String,Symbol]])
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : scala.collection.immutable.Map[Int,Product with Serializable with scala.util.Either[String,Symbol]]
 required: ?M
              extractEither(map)
              ^
<console>:20: error: type mismatch;
 found   : scala.collection.immutable.Map[Int,Product with Serializable with scala.util.Either[String,Symbol]]
 required: M[(Key, Either[TLeft,TRight])]
              extractEither(map)
                            ^
<console>:20: error: Cannot construct a collection of type M[(Key, TRight)] with elements of type (Key, TRight) based on a collection of type M[(Key, Either[TLeft,TRight])].
              extractEither(map)
                           ^

Atempt #2

This one is restricted to maps, mutable or immutable.

def extractEither[
  Key, TLeft, TRight, M <: collection.Map[Key, Either[TLeft, TRight]]
](map: M): Either[TLeft, M] = {
  Right[TLeft, M](map.map { case (key, either) =>
    either.fold(
      leftVal => return Left(leftVal),
      rightVal => key -> rightVal
    )
  }.asInstanceOf[M])
}

This fails with:

scala> extractEither(map)
<console>:20: error: inferred type arguments [Nothing,Nothing,Nothing,scala.collection.immutable.Map[Int,Product with Serializable with scala.util.Either[String,Symbol]]] do not conform to method extractEither's type parameter bounds [Key,TLeft,TRight,M <: scala.collection.Map[Key,Either[TLeft,TRight]]]
              extractEither(map)
              ^
<console>:20: error: type mismatch;
 found   : scala.collection.immutable.Map[Int,Product with Serializable with scala.util.Either[String,Symbol]]
 required: M
              extractEither(map)
                            ^

Working non-generic solution

  def extractEither[
    Key, TLeft, TRight
  ](map: Map[Key, Either[TLeft, TRight]]): Either[TLeft, Map[Key, TRight]] = {
    Right(map.map { case (key, either) =>
      either.fold(
        leftVal => return Left(leftVal),
        rightVal => key -> rightVal
      )
    })
  }

But this is not generic at all :|

Can anyone shed some light on how to write this properly?

Answer 1

First solution is almost there, but you should use M[X] <: TraversableOnce[X] to avoid having to cast. And you need to type hint to the compiler to get the type of the map correct, either when you pass it to the method or when you define it.

scala> def extractEither[K, L, R, M[X] <: TraversableOnce[X]](monad: M[(K, Either[L, R])])(implicit cbf: CanBuildFrom[M[(K, Either[L, R])], (K, R), M[(K, R)]]): Either[L, M[(K, R)]] = {
 val builder = cbf(monad)
 builder.sizeHint(monad.size)
 monad.foreach({x =>
 val (key, either) = x
 either.fold(
 leftVal => return Left(leftVal),
 rightVal => builder += ((key, rightVal))
 )})
 Right(builder.result())
 }
warning: there were 1 feature warning(s); re-run with -feature for details
extractEither: [K, L, R, M[X] <: TraversableOnce[X]](monad: M[(K, Either[L,R])])(implicit cbf: scala.collection.generic.CanBuildFrom[M[(K, Either[L,R])],(K, R),M[(K, R)]])Either[L,M[(K, R)]]

scala> val map = Map(1 -> Left("foo"), 2 -> Right('bar), 3 -> Right('baz))
map: scala.collection.immutable.Map[Int,Product with Serializable with scala.util.Either[String,Symbol]] = Map(1 -> Left(foo), 2 -> Right('bar), 3 -> Right('baz))

scala> extractEither(map: TraversableOnce[(Int, Either[String, Symbol])])
res2: Either[String,TraversableOnce[(Int, Symbol)]] = Left(foo)

scala> val map2: Map[Int, Either[String, Symbol]] = Map(1 -> Left("foo"), 2 -> Right('bar), 3 -> Right('baz))
map2: Map[Int,Either[String,Symbol]] = Map(1 -> Left(foo), 2 -> Right('bar), 3 -> Right('baz))

scala> extractEither(map2)
res3: Either[String,scala.collection.immutable.Iterable[(Int, Symbol)]] = Left(foo)