array - Trabajar con colecciones de Scala-CanBuildFrom problem

scala::

Question

Estoy tratando de escribir un método que acepte cualquier tipo de colección CC[_] y lo asigne a una nueva colección (el mismo tipo de colección pero un tipo de elemento diferente) y estoy luchando de manera real. Básicamente estoy tratando de implementar el map pero no en la colección en sí .

La pregunta

Estoy tratando de implementar un método con una firma que se parece un poco a:

def map[CC[_], T, U](cct: CC[T], f: T => U): CC[U]

Su uso sería:

map(List(1, 2, 3, 4), (_ : Int).toString) //would return List[String]

Me interesa una respuesta que también funcione donde CC es Array y me interesa la razón por la que mis intentos (a continuación) no han funcionado.

Mis intentos

(Para los impacientes, en lo que sigue, no logro que esto funcione. Para reiterar, la pregunta es "¿Cómo puedo escribir un método así?")

Empiezo así:

scala> def map[T, U, CC[_]](cct: CC[T], f: T => U)(implicit cbf: CanBuildFrom[CC[T], U, CC[U]]): CC[U] = 
     | cct map f
                                                             ^
 <console>:9: error: value map is not a member of type parameter CC[T]
       cct map f
           ^

OK, eso tiene sentido, ¡necesito decir que CC es transitable!

scala> def map[T, U, X, CC[X] <: Traversable[X]](cct: CC[T], f: T => U)(implicit cbf: CanBuildFrom[CC[T], U, CC[U]]): CC[U] = 
     | cct map f
<console>:10: error: type mismatch;
 found   : Traversable[U]
 required: CC[U]
       cct map f
           ^

Err, OK! Tal vez si en realidad especifico esa instancia cbf . Después de todo, especifica el tipo de retorno ( To ) como CC[U] :

scala> def map[T, U, X, CC[X] <: Traversable[X]](cct: CC[T], f: T => U)(implicit cbf: CanBuildFrom[CC[T], U, CC[U]]): CC[U] = 
     | cct.map(t => f(t))(cbf)
<console>:10: error: type mismatch;
 found   : scala.collection.generic.CanBuildFrom[CC[T],U,CC[U]]
 required: scala.collection.generic.CanBuildFrom[Traversable[T],U,CC[U]]
       cct.map(t => f(t))(cbf)
                          ^

Err, OK! Ese es un error más específico. Parece que puedo usar eso!

scala> def map[T, U, X, CC[X] <: Traversable[X]](cct: CC[T], f: T => U)(implicit cbf: CanBuildFrom[Traversable[T], U, CC[U]]): CC[U] = 
     | cct.map(t => f(t))(cbf)
map: [T, U, X, CC[X] <: Traversable[X]](cct: CC[T], f: T => U)(implicit cbf: scala.collection.generic.CanBuildFrom[Traversable[T],U,CC[U]])CC[U]

Brillante. ¡Me tiene un map ! Vamos a usar esta cosa!

scala> map(List(1, 2, 3, 4), (_ : Int).toString)
<console>:11: error: Cannot construct a collection of type List[java.lang.String] with elements of type java.lang.String based on a collection of type Traversable[Int].
              map(List(1, 2, 3, 4), (_ : Int).toString)
                 ^

¿Que qué?

Observaciones

Realmente no puedo evitar pensar que las observaciones de Tony Morris sobre esto en ese momento fueron absolutamente acertadas. ¿Que dijo el? Dijo: " Sea lo que sea, no es un mapa ". Mira lo fácil que es esto en estilo scalaz :

scala> trait Functor[F[_]] { def fmap[A, B](fa: F[A])(f: A => B): F[B] }
defined trait Functor

scala> def map[F[_]: Functor, A, B](fa: F[A], f: A => B): F[B] = implicitly[Functor[F]].fmap(fa)(f)
map: [F[_], A, B](fa: F[A], f: A => B)(implicit evidence$1: Functor[F])F[B]

Entonces

scala> map(List(1, 2, 3, 4), (_ : Int).toString)
<console>:12: error: could not find implicit value for evidence parameter of type Functor[List]
              map(List(1, 2, 3, 4), (_ : Int).toString)
                 ^

Así que eso

scala> implicit val ListFunctor = new Functor[List] { def fmap[A, B](fa: List[A])(f: A => B) = fa map f }
ListFunctor: java.lang.Object with Functor[List] = $anon$1@4395cbcb

scala> map(List(1, 2, 3, 4), (_ : Int).toString)
res5: List[java.lang.String] = List(1, 2, 3, 4)

Memo a sí mismo: escuchar a Tony!

Answer 1

En realidad hay varias preguntas allí ...

Comencemos con su último intento:

scala> def map[T, U, X, CC[X] <: Traversable[X]](cct: CC[T], f: T => U)
 (implicit cbf: CanBuildFrom[Traversable[T], U, CC[U]]): CC[U] = 
  cct.map(t => f(t))(cbf)

Este compila pero no funciona porque, de acuerdo con su firma de tipo, tiene que buscar un objeto CanBuildFrom[Traversable[Int], String, List[String]] implícito CanBuildFrom[Traversable[Int], String, List[String]] , y simplemente no hay uno. Si fueras a crear uno a mano, funcionaría.

Ahora el intento anterior:

scala> def map[T, U, X, CC[X] <: Traversable[X]](cct: CC[T], f: T => U)
 (implicit cbf: CanBuildFrom[CC[T], U, CC[U]]): CC[U] = 
  cct.map(t => f(t))(cbf)
<console>:10: error: type mismatch;
 found   : scala.collection.generic.CanBuildFrom[CC[T],U,CC[U]]
 required: scala.collection.generic.CanBuildFrom[Traversable[T],U,CC[U]]
       cct.map(t => f(t))(cbf)
                          ^

Este no se compila porque el CanBuildFrom implícito en Traversable está codificado para aceptar solo una colección Traversable as From . Sin embargo, como se señaló en la otra respuesta, TraversableLike conoce el tipo de colección real (es su segundo parámetro de tipo), por lo que define el map con el CanBuildFrom[CC[T], U, CC[U]] adecuado y todos están contentos . En realidad, TraversableLike hereda este método de map de scala.collection.generic.FilterMonadic , por lo que esto es aún más genérico:

scala> import scala.collection.generic._
import scala.collection.generic._

scala> def map[T, U, CC[T] <: FilterMonadic[T, CC[T]]](cct: CC[T], f: T => U)
 |  (implicit cbf:  CanBuildFrom[CC[T], U, CC[U]]): CC[U] = cct.map(f)
warning: there were 1 feature warnings; re-run with -feature for details
map: [T, U, CC[T] <: scala.collection.generic.FilterMonadic[T,CC[T]]](cct: CC[T], f: T => U)(implicit cbf: scala.collection.generic.CanBuildFrom[CC[T],U,CC[U]])CC[U]

scala> map(List(1,2,3,4), (_:Int).toString + "k")
res0: List[String] = List(1k, 2k, 3k, 4k)

Finalmente, lo anterior no funciona con matrices porque Array no es un FilterMonadic . Pero hay una conversión implícita de Array a ArrayOps , y la última implementa FilterMonadic . Entonces, si agrega una vista enlazada allí, obtendrá algo que también funciona para los arreglos:

scala> import scala.collection.generic._
import scala.collection.generic._

scala> def map[T, U, CC[T]](cct: CC[T], f: T => U)
 |  (implicit cbf:  CanBuildFrom[CC[T], U, CC[U]], 
 |   ev: CC[T] => FilterMonadic[T,CC[T]]): CC[U] = cct.map(f)
warning: there were 1 feature warnings; re-run with -feature for details
map: [T, U, CC[T]](cct: CC[T], f: T => U)(implicit cbf: scala.collection.generic.CanBuildFrom[CC[T],U,CC[U]], implicit ev: CC[T] => scala.collection.generic.FilterMonadic[T,CC[T]])CC[U]

scala> map(List(1,2,3,4), (_:Int).toString + "k")
res0: List[String] = List(1k, 2k, 3k, 4k)

scala> map(Array(1,2,3,4), (_:Int).toString + "k")
res1: Array[String] = Array(1k, 2k, 3k, 4k)

EDITAR: También hay una manera de hacer que funcione para String and co: simplemente elimine los tipos más altos en la colección de entrada / salida, utilizando un tercero en el medio:

def map[T, U, From, To, Middle](cct: From, f: T => U)
 (implicit ev: From => FilterMonadic[T, Middle], 
  cbf: CanBuildFrom[Middle,U,To]): To = cct.map(f)

Esto funciona en String e incluso en el Map[A,B] :

scala> map(Array(42,1,2), (_:Int).toString)
res0: Array[java.lang.String] = Array(42, 1, 2)

scala> map(List(42,1,2), (_:Int).toString)
res1: List[java.lang.String] = List(42, 1, 2)

scala> map("abcdef", (x: Char) => (x + 1).toChar)
res2: String = bcdefg

scala> map(Map(1 -> "a", 2 -> "b", 42 -> "hi!"), (a:(Int, String)) => (a._2, a._1))
res5: scala.collection.immutable.Map[String,Int] = Map(a -> 1, b -> 2, hi! -> 42)

Probado con 2.9.2. Pero como jsuereth señaló, hay un maravilloso IsTraversableLike en 2.10 que está mejor preparado para esto.

Answer 2

Es esto

def map[A,B,T[X] <: TraversableLike[X,T[X]]]
  (xs: T[A])(f: A => B)(implicit cbf: CanBuildFrom[T[A],B,T[B]]): T[B] = xs.map(f)

map(List(1,2,3))(_.toString)
// List[String] = List(1, 2, 3)

Véase también esta pregunta .

Answer 3

Lo que está ejecutando no es necesariamente CanBuildFrom , o el problema Array vs. Seq . Se está ejecutando en String que no es de tipo superior, pero admite map contra sus Char s.

SO: Primero una digresión en el diseño de la colección de Scala.

Lo que necesita es una forma de inferir tanto el tipo de colección (por ejemplo, String , Array[Int] , List[Foo] ) como el tipo de elemento (por ejemplo, Char , Int , Foo correspondiente a lo anterior).

Scala 2.10.x ha agregado algunas "clases de tipo" para ayudarlo. Por ejemplo, puedes hacer lo siguiente:

class FilterMapImpl[A, Repr](val r: GenTraversableLike[A, Repr]) {
  final def filterMap[B, That](f: A => Option[B])(implicit cbf: CanBuildFrom[Repr, B, That]): That =
    r.flatMap(f(_).toSeq)
 }
 implicit def filterMap[Repr, A](r: Repr)(implicit fr: IsTraversableOnce[Repr]): FilterMapImpl[fr.A,Repr] =
   new FilterMapImpl(fr.conversion(r))

Hay dos piezas aquí. PRIMERO, su clase que usa colecciones necesita dos parámetros de tipo: El tipo específico de la colección Repr y el tipo de los elementos A

A continuación, define un método implícito que solo toma el tipo de colección Repr . Utiliza IsTraversableOnce (nota: también hay un IsTraversableLike ) para capturar el tipo de elemento de esa colección. Usted ve esto usado en la firma de tipo FilterMapImpl[Repr, fr.A] .

Ahora, parte de esto se debe a que Scala no usa la misma categoría para todas sus operaciones "tipo funtor". Específicamente, el map es un método útil para String . Puedo ajustar todos los personajes. Sin embargo, String solo puede ser un Seq[Char] . Si quiero definir un Functor , entonces mi categoría solo puede contener el tipo Char y las flechas Char => Char . Esta lógica se captura en CanBuildFrom . Sin embargo, dado que una String es una Seq[Char] , si intenta usar un map en la categoría admitida por el método del map Seq , CanBuildFrom alterará su llamada al map .

Básicamente estamos definiendo una relación de "herencia" para nuestras categorías. Si intenta utilizar el patrón de Functor , colocamos la firma de tipo en la categoría más específica que podemos conservar. Llámalo como quieras; Eso es un gran factor de motivación para el diseño de la colección actual.

End Digression, responde la pregunta.

Ahora, debido a que estamos tratando de inferir muchos tipos al mismo tiempo, creo que esta opción tiene la menor cantidad de anotaciones de tipo:

import collection.generic._

def map[Repr](col: Repr)(implicit tr: IsTraversableLike[Repr]) = new {
  def apply[U, That](f: tr.A => U)(implicit cbf: CanBuildFrom[Repr, U, That]) = 
    tr.conversion(col) map f
}


scala> map("HI") apply (_ + 1 toChar )
warning: there were 2 feature warnings; re-run with -feature for details
res5: String = IJ

La pieza importante a tener en cuenta aquí es que IsTraversableLike captura una conversión de Repr a TraversableLike que le permite usar el método de map .

opcion 2

También dividimos un poco el método de llamada para que Scala pueda inferir los tipos Repr y U antes de definir nuestra función anónima. Para evitar anotaciones de tipo en funciones anónimas, debemos tener todos los tipos conocidos antes de que aparezcan. Ahora, aún podemos hacer que Scala deduzca algunos tipos, pero perderemos cosas que se pueden Traversable implícita si hacemos esto:

import collection.generic._
import collection._
def map[Repr <: TraversableLike[A, Repr], A, U, That](col: Repr with TraversableLike[A,Repr])(f: A => U)(implicit cbf: CanBuildFrom[Repr, U, That]) = 
    col map f

Tenga en cuenta que tenemos que usar Repr with TraversableLike[A,Repr] . Parece que la mayoría de los tipos con límite de F requieren este malabarismo.

En cualquier caso, ahora veamos qué sucede en algo que se extiende a Traversable :

scala> map(List(40,41))(_ + 1 toChar )
warning: there were 1 feature warnings; re-run with -feature for details
res8: List[Char] = List(), *)

Eso es genial. Sin embargo, si queremos el mismo uso para Array y String , tenemos que trabajar un poco más:

scala> map(Array(''H'', ''I''): IndexedSeq[Char])(_ + 1 toChar)(breakOut): Array[Char]
warning: there were 1 feature warnings; re-run with -feature for details
res14: Array[Char] = Array(I, J)

scala> map("HI": Seq[Char])(_ + 1 toChar)(breakOut) : String
warning: there were 1 feature warnings; re-run with -feature for details
res11: String = IJ

Hay dos piezas para este uso:

1. Tenemos que usar una anotación de tipo para la conversión implícita de String / Array → Seq / IndexedSeq .
2. Tenemos que usar breakOut para nuestro CanBuildFrom y anotar el valor de retorno esperado.

Esto se debe únicamente a que el tipo Repr <: TraversableLike[A,Repr] no incluye String o Array , ya que estos utilizan conversiones implícitas.

Opcion 3

Puede colocar todas las implicaciones juntas al final y requerir que el usuario anote los tipos. No es la solución más elegante, así que creo que evitaré publicarla a menos que realmente quiera verla.

Entonces, básicamente, si quieres incluir String y Array[T] como colecciones, tienes que saltar a través de algunos aros. Esta restricción de categoría para el mapa se aplica a los functores String y BitSet en Scala.

Espero que eso ayude. Hazme un ping si tienes más preguntas.