mapValues ​​на самой внутренней карте вложенных карт

Question

Это вдохновение возникло, когда я попытался ответить на этот .

Скажем, у вас есть последовательность данных (например, из файла CSV). groupBy может использоваться для анализа определенного аспекта данных, группирования по столбцу или комбинации столбцов. Например:

val groups0: Map[String, Array[String]] = 
  seq.groupBy(row => row(0) + "-" + row(4))

Если я затем хочу создать подгруппы внутри групп, я могу сделать

val groups1: Map[String, Map[String, Array[String]]] = 
  groups0.mapValues(row => row.groupBy(_(1))

Если я захочу сделать это еще раз, это станет действительно громоздким:

val groups2 = 
  groups1.mapValues(groups => groups.mapValues(row => row.groupBy(_(2)))

Итак, вот мой вопрос, учитывая произвольную вложенность Map[K0, Map[K1, ..., Map[Kn, V]]], как вы пишете mapValues функцию, которая принимает f: (V) => B и применяется к внутреннему V, чтобы вернуть Map[K0, Map[K1, ..., Map[Kn, B]]]?

Answer 1

Мой первый инстинкт сказал, что обработка произвольного вложения безопасным для типов способом была бы невозможна, но кажется, что это возможно, если вы определите несколько следствий, которые сообщают компилятору, как это сделать.
По сути, «простой» маппер говорит ему, как обращаться с простым не вложенным случаем, а «wrappedMapper» говорит ему, как детализировать один слой карты:

  // trait to tell us how to map inside of a container.
  trait CanMapInner[WrappedV, WrappedB,V,B] {
    def mapInner(in: WrappedV, f: V => B): WrappedB
  }

  // simple base case (no nesting involved).
  implicit def getSimpleMapper[V,B] = new CanMapInner[V,B,V,B] {
    def mapInner(in: V, f: (V) => B): B = f(in)
  }

  // drill down one level of "Map".
  implicit def wrappedMapper[K,V,B,InnerV,InnerB]
    (implicit innerMapper: CanMapInner[InnerV,InnerB,V,B]) =
    new CanMapInner[Map[K,InnerV], Map[K,InnerB],V,B] {
      def mapInner(in: Map[K, InnerV], f: (V) => B): Map[K, InnerB] =
        in.mapValues(innerMapper.mapInner(_, f))
    }

  // the actual implementation.
  def deepMapValues[K,V,B,WrappedV,WrappedB](map: Map[K,WrappedV], f: V => B)
      (implicit mapper: CanMapInner[WrappedV,WrappedB,V,B]) = {
    map.mapValues(inner => mapper.mapInner(inner, f))
  }

  // testing with a simple map
  {
    val initMap = Map(1 -> "Hello", 2 -> "Goodbye")
    val newMap = deepMapValues(initMap, (s: String) => s.length)
    println(newMap) // Map(1 -> 5, 2 -> 7)
  }

  // testing with a nested map
  {
    val initMap = Map(1 -> Map("Hi" -> "Hello"), 2 -> Map("Bye" -> "Goodbye"))
    val newMap = deepMapValues(initMap, (s: String) => s.length)
    println(newMap) // Map(1 -> Map(Hi -> 5), 2 -> Map(Bye -> 7))
  }

Конечно, в реальном коде динамическое решение для сопоставления с образцом ужасно заманчиво благодаря своей простоте. Безопасность типов - это еще не все:)

Answer 2

Я уверен, что есть лучший способ использования Manifest, но сопоставление с образцом, кажется, различает Seq и Map, поэтому вот оно:

object Foo {
  def mapValues[A <: Map[_, _], C, D](map: A)(f: C => D): Map[_, _] = map.mapValues {
    case seq: Seq[C] => seq.groupBy(f)
    case innerMap: Map[_, _] => mapValues(innerMap)(f)
  }
}

scala> val group0 = List("fooo", "bar", "foo") groupBy (_(0))
group0: scala.collection.immutable.Map[Char,List[java.lang.String]] = Map((f,List(fooo, foo)), (b,List(bar)))

scala> val group1 = Foo.mapValues(group0)((x: String) => x(1))
group1: scala.collection.immutable.Map[_, Any] = Map((f,Map(o -> List(fooo, foo))), (b,Map(a -> List(bar))))

scala> val group2 = Foo.mapValues(group1)((x: String) => x(2))
group2: scala.collection.immutable.Map[_, Any] = Map((f,Map(o -> Map(o -> List(fooo, foo)))), (b,Map(a -> Map(r -> List(bar)))))

Редактировать : Вот типизированная версия, использующая тип с более высоким родом.

trait NestedMapValue[Z] {
  type Next[X] <: NestedMapValue[Z]
  def nextValues[D](f: Z => D): Next[D]
}

trait NestedMap[Z, A, B <: NestedMapValue[Z]] extends NestedMapValue[Z] { self =>
  type Next[D] = NestedMap[Z, A, B#Next[D]]

  val map: Map[A, B]
  def nextValues[D](f: Z => D): Next[D] = self.mapValues(f)

  def mapValues[D](f: Z => D): NestedMap[Z, A, B#Next[D]] = new NestedMap[Z, A, B#Next[D]] { val map = self.map.mapValues {
    case x: B => x.nextValues[D](f)
  }}

  override def toString = "NestedMap(%s)" format (map.toString)
}

trait Bottom[A] extends NestedMapValue[A] {
  type Next[D] = NestedMap[A, D, Bottom[A]]

  val seq: Seq[A]
  def nextValues[D](f: A => D): Next[D] = seq match {
    case seq: Seq[A] => groupBy[D](f)
  }

  def groupBy[D](f: A => D): Next[D] = seq match {
    case seq: Seq[A] => 
      new NestedMap[A, D, Bottom[A]] { val map = seq.groupBy(f).map { case (key, value) => (key, new Bottom[A] { val seq = value })} }  
  }

  override def toString = "Bottom(%s)" format (seq.toString) 
}

object Bottom {
  def apply[A](aSeq: Seq[A]) = new Bottom[A] { val seq = aSeq }
}

scala> val group0 = Bottom(List("fooo", "bar", "foo")).groupBy(x => x(0))
group0: NestedMap[java.lang.String,Char,Bottom[java.lang.String]] = NestedMap(Map(f -> Bottom(List(fooo, foo)), b -> Bottom(List(bar))))

scala> val group1 = group0.mapValues(x => x(1))
group1: NestedMap[java.lang.String,Char,Bottom[java.lang.String]#Next[Char]] = NestedMap(Map(f -> NestedMap(Map(o -> Bottom(List(fooo, foo)))), b -> NestedMap(Map(a -> Bottom(List(bar))))))

scala> val group2 = group1.mapValues(x => x.size)
group2: NestedMap[java.lang.String,Char,Bottom[java.lang.String]#Next[Char]#Next[Int]] = NestedMap(Map(f -> NestedMap(Map(o -> NestedMap(Map(4 -> Bottom(List(fooo)), 3 -> Bottom(List(foo)))))), b -> NestedMap(Map(a -> NestedMap(Map(3 -> Bottom(List(bar))))))))