How do I use the type member A in IsTraversableLike?

Question

I am trying to write some extension methods for the Scala collections, and running into trouble fully generifying them.

A first attempt at tailOption yields something like:

implicit class TailOption[A, Repr <: GenTraversableLike[A, Repr]](val repr: Repr) {
  def tailOption: Option[Repr] = 
    if (repr.isEmpty) None 
    else Some(repr.tail)
}

unfortunately, this doesn't work:

scala> List(1,2,3).tailOption
<console>:19: error: value tailOption is not a member of List[Int]
              List(1,2,3).tailOption

Scala 2.10 provides the IsTraversableLike type-class to help adapt this sort of thing for all collections (including odd ones, like Strings).

With this I can for instance implement tailOption quite easily:

implicit class TailOption[Repr](val r: Repr)(implicit fr: IsTraversableLike[Repr]) {
  def tailOption: Option[Repr] = { 
    val repr = fr.conversion(r)
    if (repr.isEmpty) None 
    else Some(repr.tail)
  }
}

scala> List(1,2,3).tailOption
res12: Option[List[Int]] = Some(List(2, 3))

scala> "one".tailOption
res13: Option[String] = Some(ne)

The result is of the correct type: Option[<input-type>]. Specifically, I have been able to preserve the Repr type when calling methods that return Repr, like `tail.

Unfortunately, I can't seem to use this trick to preserve the type of the elements of the collection. I can't call methods that return an element.

IsTraversableLike does have a member A but it doesn't seem very useful. In particular I can't reconstruct my original element type and the member is not equivalent in type. For instance, without further work, headTailOption looks like this:

implicit class HeadTailOption[Repr](val r: Repr)(implicit val fr: IsTraversableLike[Repr]) { 
  def headTailOption: Option[(fr.A, Repr)] = { 
    val repr = fr.conversion(r)
    if (repr.isEmpty) None 
    else Some(repr.head -> repr.tail)
  }
}

scala> val Some((c, _)) = "one".headTailOption
c: _1.fr.A forSome { val _1: HeadTailOption[String] } = o

As we can see, c has a wonderfully baroque type. But, this type is not equivalent to Char:

scala> val fr = implicitly[IsTraversableLike[String]]
fr: scala.collection.generic.IsTraversableLike[String] = scala.collection.generic.IsTraversableLike$$anon$1@60ab6a84

scala> implicitly[fr.A <:< Char]
<console>:25: error: Cannot prove that fr.A <:< Char.
              implicitly[fr.A <:< Char]

I have tried all sorts of tricks including having Repr[A] <: GenTraversableLike[A, Repr[A]] none of which help. Can anyone work out the magic sauce to make headTailOption return the right types for:

val headTailString: Option[(Char, String)] = "one".headTailOption
val headTailList: Option[(Int, List[Int])] = List(1,2,3).headTailOption

Answer 1

A partial answer. You have probably started from the scaladoc example for IsTraversableLike. It still uses the "old approach" of separating implicit conversion and instantiating the wrapper class, instead of going in one step through an implicit class. It turns out that the "old approach" does work:

import collection.GenTraversableLike
import collection.generic.IsTraversableLike

final class HeadTailOptionImpl[A, Repr](repr: GenTraversableLike[A, Repr]) { 
  def headTailOption: Option[(A, Repr)] = { 
    if (repr.isEmpty) None 
    else Some(repr.head -> repr.tail)
  }
}

implicit def headTailOption[Repr](r: Repr)(implicit fr: IsTraversableLike[Repr]):
  HeadTailOptionImpl[fr.A,Repr] = new HeadTailOptionImpl(fr.conversion(r))

// `c` looks still weird: `scala.collection.generic.IsTraversableLike.stringRepr.A`
val Some((c, _)) = "one".headTailOption
val d: Char = c  // ...but it really is a `Char`!

val headTailString: Option[(Char, String)] = "one".headTailOption
val headTailList: Option[(Int, List[Int])] = List(1,2,3).headTailOption

---

As Miles points out, the split seems essential for this to work with the implicit search and type inference.

Another solution, although of course less elegant, is to give up the unification of strings and collections:

trait HeadTailOptionLike[A, Repr] {
  def headTailOption: Option[(A, Repr)]
}

implicit class GenHeadTailOption[A, Repr](repr: GenTraversableLike[A, Repr])
extends HeadTailOptionLike[A, Repr] {
  def headTailOption = 
    if (repr.isEmpty) None 
    else Some(repr.head -> repr.tail)
}

implicit class StringHeadTailOption(repr: String)
extends HeadTailOptionLike[Char, String] {
  def headTailOption = 
    if (repr.isEmpty) None 
    else Some(repr.head -> repr.tail) // could use repr.charAt(0) -> repr.substring(1)
}

List(1,2,3).headTailOption
"one".headTailOption