Могу я “сутенер моя библиотека” с аналогом TraversableLike.map, который имеет приятно различные типы?

Вы не можете сделать это для всех Traversable, поскольку они не гарантируют, что map возвращает что-то более конкретное, чем Traversable. См. обновление 2 ниже.

import collection.generic.CanBuildFrom
import collection.TraversableLike

class TraversableW[CC[X] <: TraversableLike[X, CC[X]], A](value: CC[A]) {
  def mapmap(f: A => A)(implicit cbf: CanBuildFrom[CC[A], A, CC[A]]): CC[A] 
      = value.map(f andThen f)
  def mapToString(implicit cbf: CanBuildFrom[CC[A], String, CC[String]]): CC[String]
      = value.map(_.toString)
}

object TraversableW {
  implicit def TraversableWTo[CC[X] <: TraversableLike[X, CC[X]], A](t: CC[A]): TraversableW[CC, A] 
      = new TraversableW[CC, A](t)
}

locally {
  import TraversableW._

  List(1).mapmap(1+)
  List(1).mapToString
  // The static type of Seq is preserved, *and* the dynamic type of List is also
  // preserved.
  assert((List(1): Seq[Int]).mapmap(1+) == List(3))
}

ОБНОВЛЕНИЕ. Я добавил еще один пимповый метод, mapToString, чтобы продемонстрировать, почему TraversableW принимает два параметра типа, а не один, как в решении Алексея. Параметр CC является типом более высокого рода, он представляет собой тип контейнера исходной коллекции. Второй параметр, A, представляет тип элемента исходной коллекции. Таким образом, метод mapToString способен вернуть исходный тип контейнера с другим типом элемента: CC[String.

ОБНОВЛЕНИЕ 2. Благодаря комментарию @oxbow_lakes я переосмыслил это. Действительно, можно напрямую пимповать CC[X] <: Traversable[X], TraversableLike не является строго необходимым. Комментарии inline:

import collection.generic.CanBuildFrom
import collection.TraversableLike

class TraversableW[CC[X] <: Traversable[X], A](value: CC[A]) {
  /**
   * A CanBuildFromInstance based purely the target element type `Elem`
   * and the target container type `CC`. This can be converted to a
   * `CanBuildFrom[Source, Elem, CC[Elem]` for any type `Source` by
   * `collection.breakOut`.
   */
  type CanBuildTo[Elem, CC[X]] = CanBuildFrom[Nothing, Elem, CC[Elem]]

  /**
   * `value` is _only_ known to be a `Traversable[A]`. This in turn
   * turn extends `TraversableLike[A, Traversable[A]]`. The signature
   * of `TraversableLike#map` requires an implicit `CanBuildFrom[Traversable[A], B, That]`,
   * specifically in the call below `CanBuildFrom[Traversable[A], A CC[A]`.
   *
   * Essentially, the specific type of the source collection is not known in the signature
   * of `map`.
   *
   * This cannot be directly found instead we look up a `CanBuildTo[A, CC[A]]` and
   * convert it with `collection.breakOut`
   *
   * In the first example that referenced `TraversableLike[A, CC[A]]`, `map` required a
   * `CanBuildFrom[CC[A], A, CC[A]]` which could be found.
   */
  def mapmap(f: A => A)(implicit cbf: CanBuildTo[A, CC]): CC[A]
      = value.map[A, CC[A]](f andThen f)(collection.breakOut)
  def mapToString(implicit cbf: CanBuildTo[String, CC]): CC[String]
      = value.map[String, CC[String]](_.toString)(collection.breakOut)
}

object TraversableW {
  implicit def TraversableWTo[CC[X] <: Traversable[X], A](t: CC[A]): TraversableW[CC, A]
      = new TraversableW[CC, A](t)
}

locally {
  import TraversableW._

  assert((List(1)).mapmap(1+) == List(3))

  // The static type of `Seq` has been preserved, but the dynamic type of `List` was lost.
  // This is a penalty for using `collection.breakOut`. 
  assert((List(1): Seq[Int]).mapmap(1+) == Seq(3))   
}

В чем разница? Нам пришлось использовать collection.breakOut, потому что мы не можем восстановить конкретный подтип коллекции из простого Traversable[A].

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  val b = bf(repr)
  b.sizeHint(this) 
  for (x <- this) b += f(x)
  b.result
}

Конструктор Builder b инициализируется исходной коллекцией, что является механизмом сохранения динамического типа через map. Однако наш CanBuildFrom отрекся от всех знаний о From, посредством аргумента типа Nothing. Все, что можно сделать с Nothing - это игнорировать его, что и делает breakOut:

def breakOut[From, T, To](implicit b : CanBuildFrom[Nothing, T, To]) =
  new CanBuildFrom[From, T, To] {
    def apply(from: From) = b.apply();
    def apply() = b.apply()
  }

Мы не можем вызвать b.apply(from), не более чем def foo(a: Nothing) = 0.