使用scala集合 - CanBuildFrom麻烦

Question

我正在尝试编写一个方法,它接受任何类型的集合CC[_]并将其映射到一个新的集合(相同的集合类型,但不同的元素类型),我正在挣扎皇家.基本上我正在尝试实现map但不是集合本身.

问题

我正在尝试使用签名实现一个看起来有点像的方法:

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

它的用法是:

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

我感兴趣的答案也将在哪里工作CC是Array我很感兴趣,我尝试(下)都最终没有奏效的原因.

---

我的尝试

(对于不耐烦的人,在接下来的内容中,我完全没有让它发挥作用.重申一下,问题是"我怎么能写出这样的方法？")

我这样开头:

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
           ^

好的,这是有道理的 - 我需要说这CC是可以穿越的!

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
           ^

呃,好的!也许如果我确实指定了那个cbf实例.毕竟,它将返回类型(To)指定为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)
                          ^

呃,好的!这是一个更具体的错误.看起来我可以用它!

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]

辉煌.我有一个map!让我们用这个东西吧!

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

说什么？

---

意见

我真的情不自禁地认为Tony Morris当时对此的观察是绝对的.他说什么？他说" 不管是什么,都不是地图 ".看看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]

然后

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

以便

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)

给自己的备忘录:听托尼!

Answer 1

什么你正在运行到不一定CanBuildFrom本身,或Array与Seq问题.您正在运行到String这是不是更高kinded,但支持map针对其Char秒.

SO:首先是Scala的收藏设计.

你需要的是既推断集合类型(例如一个方法String,Array[Int],List[Foo])和元素类型(例如Char,Int,Foo对应于上述).

Scala 2.10.x添加了一些"类型类"来帮助您.例如,您可以执行以下操作:

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

这里有两件.首先,使用集合的类需要两个类型参数:集合的特定类型Repr和元素的类型A.

接下来,定义一个仅采用集合类型的隐式方法Repr.您可以使用IsTraversableOnce(注意:还有一个IsTraversableLike)来捕获该集合的元素类型.您会在类型签名中看到这一点FilterMapImpl[Repr, fr.A].

现在,部分原因是因为Scala并没有对所有类似"仿函数"的操作使用相同的类别.具体来说,map是一种有用的方法String.我可以调整所有角色.但是,String只能是一个Seq[Char].如果我想定义一个Functor,那么我的类别只能包含类型Char和箭头Char => Char.这个逻辑被捕获CanBuildFrom.然而,由于String是Seq[Char],如果你尝试使用map在所支持的类别Seq的map方法,然后CanBuildFrom将改变您的来电map.

我们实质上是为我们的类别定义"继承"关系.如果您尝试使用该Functor模式,我们会将类型签名删除到我们可以保留的最具体的类别.称之为你的意思; 这是当前系列设计的一个重要推动因素.

结束题词,回答问题

现在,因为我们试图同时推断出很多类型,我认为这个选项具有最少的类型注释:

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

这里需要注意的重要一点是IsTraversableLike捕获从转换Repr到TraversableLike允许您使用该map方法的转换.

选项2

我们也拆分方法调用一下,让斯卡拉可以推断的类型Repr和U我们定义匿名函数之前.为了避免对匿名函数类型的注释,我们必须拥有所有类型的已知它出现之前.现在,我们仍然可以让Scala推断出一些类型,但如果我们这样做,就会丢失隐含的 东西Traversable:

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

请注意,我们必须使用Repr with TraversableLike[A,Repr].似乎大多数F-bounded类型都需要这种杂耍.

在任何情况下,现在让我们看看在扩展的东西上会发生什么Traversable:

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

那很棒.然而,如果我们想为相同的使用Array和String,我们必须去更多的工作:

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

这个用法分为两部分:

1. 我们必须使用类型注释来进行String/ Array→ Seq/ 的隐式转换IndexedSeq.
2. 我们必须使用breakOutfor CanBuildFrom和type-annotate期望的返回值.

这完全是因为类型Repr <: TraversableLike[A,Repr]不包含String或Array,因为那些使用隐式转换.

选项3

您可以将所有隐含放在最后,并要求用户注释类型.不是最优雅的解决方案,所以我想我会避免发布它,除非你真的想看到它.

所以,基本上如果你想包括String和Array[T]作为集合,你必须跳过一些箍.地图的此类别限制适用于Scala中的两者String和BitSet仿函数.

我希望有所帮助.如果您还有其他问题,请告诉我.

Answer 2

实际上有几个问题......

让我们从你的最后一次尝试开始:

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)

这个确实编译但不起作用,因为根据你的类型签名,它必须寻找一个隐含CanBuildFrom[Traversable[Int], String, List[String]]的范围,而不是一个.如果您要手动创建一个,它将起作用.

现在是先前的尝试:

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

这个没有编译,因为隐式CanBuildFromin Traversable是硬编码只接受Traversableas From集合.但是,正如另一个答案中所指出的,TraversableLike知道实际的集合类型(它是它的第二个类型参数),所以它定义map正确CanBuildFrom[CC[T], U, CC[U]],每个人都很高兴.实际上,TraversableLike继承了这个map方法scala.collection.generic.FilterMonadic,所以这更通用:

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)

最后,上面不适用于数组,因为Array它不是FilterMonadic.但有从隐式转换Array到ArrayOps,而后者器具FilterMonadic.因此,如果你在那里添加一个绑定的视图,你也可以获得适用于数组的东西:

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)

编辑: 还有一种方法可以使它工作String和合作:只需删除输入/输出集合中的更高种类,使用中间的第三个:

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)

这适用于String甚至是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)

用2.9.2测试.但正如jsuereth指出的那样,IsTraversableLike2.10中的精彩更适合这一点.

Answer 3

是这个吗？

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)

另见这个问题.