如何在Scala中编写这个递归的groupBy函数

Question

最近我遇到了一个非常有用的groupBy函数,Groovy在Iterable上提供了这个函数:

public static Map groupBy(Iterable self, List<Closure> closures)

您可以使用它来执行列表甚至地图上的递归groupBy,请参阅mrhaki此处的示例

我想编写一个在Scala中执行相同操作的函数.但刚刚开始我的Scala之旅,我对于如何定义和实现此方法感到很遗憾.特别是函数的泛型方面和此方法签名的返回类型超出了我的水平.

我需要更有经验的Scala开发人员来帮助我.

以下签名是完全错误还是我在球场？

def groupBy[A, K[_]](src: List[A], fs: Seq[(A) ? K[_]]): Map[K[_], List[A]]

另外,如何使用正确的类型实现递归？

Answer 1

这是一个简单的多组实现:

implicit class GroupOps[A](coll: Seq[A]) {
  def groupByKeys[B](fs: (A => B)*): Map[Seq[B], Seq[A]] =
    coll.groupBy(elem => fs map (_(elem)))
}

val a = 1 to 20

a.groupByKeys(_ % 3, _ % 2) foreach println

如果你真的需要一些递归类型,你需要一个包装器:

sealed trait RecMap[K, V]

case class MapUnit[K, V](elem: V) extends RecMap[K, V] {
  override def toString = elem.toString()
}
case class MapLayer[K, V](map: Map[K, RecMap[K, V]]) extends RecMap[K, V] {
  override def toString = map.toString()
}

定义更改为:

implicit class GroupOps[A](coll: Seq[A]) {
  def groupByKeys[B](fs: (A => B)*): Map[Seq[B], Seq[A]] =
    coll.groupBy(elem => fs map (_(elem)))

  def groupRecursive[B](fs: (A => B)*): RecMap[B, Seq[A]] = fs match {
    case Seq() => MapUnit(coll)
    case f +: fs => MapLayer(coll groupBy f mapValues {_.groupRecursive(fs: _*)})
  }
}

并 a.groupRecursive(_ % 3, _ % 2)产生与问题更相关的东西

最后我从引用的文章重建域定义:

case class User(name: String, city: String, birthDate: Date) {
  override def toString = name
}

implicit val date = new SimpleDateFormat("yyyy-MM-dd").parse(_: String)
val month = new SimpleDateFormat("MMM").format (_:Date)

val users = List(
  User(name = "mrhaki", city = "Tilburg"  , birthDate = "1973-9-7"),
  User(name = "bob"   , city = "New York" , birthDate = "1963-3-30"),
  User(name = "britt" , city = "Amsterdam", birthDate = "1980-5-12"),
  User(name = "kim"   , city = "Amsterdam", birthDate = "1983-3-30"),
  User(name = "liam"  , city = "Tilburg"  , birthDate = "2009-3-6")
)

现在我们可以写了

users.groupRecursive(_.city, u => month(u.birthDate))

得到

地图(Tilburg - >地图(Mar - > List(liam),Sep - > List(mrhaki)),纽约 - >地图(Mar - > List(bob)),阿姆斯特丹 - >地图(Mar - > List(kim) ),May - > List(britt)))