¿Puedo "proxenetismo mi biblioteca" con un análogo de TraversableLike.map que tiene bonitos tipos de variantes?

Question

Supongamos que deseo agregar funcionalidad como map a un Scala List, algo similar a list mapmap f, que aplica la función a cada elemento de list dos veces. (Un ejemplo más grave podría ser la implementación de un mapa paralelo o distribuido, pero no quiero que se distraiga con detalles en esa dirección.)

Mi primer enfoque sería

object MapMap { 
    implicit def createFancyList[A](list: List[A]) = new Object { 
     def mapmap(f: A => A): List[A] = { list map { a: A => f(f(a)) } } 
    } 
} 

esto ahora funciona muy bien

scala> import MapMap._ 
import MapMap._ 

scala> List(1,2,3) mapmap { _ + 1 } 
res1: List[Int] = List(3, 4, 5) 

excepto, por supuesto que es sólo para List s, y no hay razón para que no quieres que esto funcione para nada Traverseable, con una función map, por ejemplo, Set s o Stream s. Por lo que el segundo intento se parece

object MapMap2 { 
    implicit def createFancyTraversable[A](t: Traversable[A]) = new Object { 
     def mapmap(f: A => A): Traversable[A] = { t map { a: A => f(f(a)) } } 
    } 
} 

Pero ahora, por supuesto, el resultado no se puede asignar a un List[A]:

scala> import MapMap2._ 
import MapMap2._ 

scala> val r: List[Int] = List(1,2,3) mapmap { _ + 1 } 
<console>:9: error: type mismatch; 
found : Traversable[Int] 
required: List[Int] 

¿Hay un término medio? ¿Puedo escribir una conversión implícita que agregue un método a todas las subclases de Traversable y devuelva con éxito objetos con ese tipo?

(estoy supongo que esto implica la comprensión de la temida CanBuildFrom rasgo, y tal vez incluso breakout!)

Answer 1

No se puede hacer esto para todos los Traversables, ya que Don No garantizamos que el mapa arroje algo más específico que Traversable. Consulte la actualización 2 a continuación.

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)) 
} 

ACTUALIZACIÓN He añadido otro método pimped, mapToString, para demostrar por qué TraversableW acepta dos parámetros de tipo, en lugar de un parámetro como en la solución de Alexey. El parámetro CC es un tipo de mayor kinder, representa el tipo de contenedor de la colección original. El segundo parámetro, A, representa el tipo de elemento de la colección original. El método mapToString puede así devolver el tipo de contenedor original con un tipo de elemento diferente: CC[String.

ACTUALIZACIÓN 2 Gracias a @oxbow_lakes comment, lo he reconsiderado. De hecho, es posible directamente chulo CC[X] <: Traversable[X], TraversableLike no es estrictamente necesario. Comentarios en línea:

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)) 
} 

¿Cuál es la diferencia?Tuvimos que usar collection.breakOut, porque no podemos recuperar el subtipo de colección específico de un mero 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 
} 

El Builderb se inicializa con la colección original, que es el mecanismo para preservar el tipo dinámico a través de un map. Sin embargo, nuestro CanBuildFrom desautorizó todo el conocimiento del De, por medio del argumento de tipo Nothing. Todo lo que se puede hacer con Nothing es ignorarlo, que es exactamente lo que hace 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() 
    } 

No podemos llamar b.apply(from), no más de lo que se podría llamar def foo(a: Nothing) = 0.

Answer 2

Como regla general, cuando se desea devolver los objetos con el mismo tipo, es necesario TraversableLike (IterableLike, SeqLike , etc.) en lugar de Traversable. Aquí está la versión más general que pudiera llegar a (la clase separada FancyTraversable está ahí para evitar la inferencia de tipos estructurales y el golpe de reflexión):

class FancyTraversable[A, S <: TraversableLike[A, S]](t: S) { 
    def mapmap(f: A => A)(implicit bf: CanBuildFrom[S,A,S]): S = { t map { a: A => f(f(a)) } } 
} 

implicit def createFancyTraversable[A, S <: TraversableLike[A, S]](t: S): FancyTraversable[A, S] = new FancyTraversable(t)