scala: Nested String Map Builder

Question

I want to create a class called NestedStrMap where it has a signature as such:

   final class NestedStrMap[A](list: List[A], first: A => String, rest: (A => String)*)

I want to write a function asMap inside of it where I can take first and rest to build a nested map. However, I can't figure out how to define the return type of this function.

  def asMap = {
    rest.toList.foldLeft(list.groupBy(first)) { (acc, i) =>
      acc.view.mapValues(l => l.groupBy(i)).toMap  // fails because the return type doesn't match
    }
  }

Here's an example of how I'd like to use it:

   case class TestResult(name: String, testType: String, score: Int)
   
   val testList = List(
     TestResult("A", "math", 75),
     TestResult("B", "math", 80),
     TestResult("B", "bio", 90),
     TestResult("C", "history", 50)
   )
   val nestedMap = NestedStrMap(testList, _.name, _.testType)
   val someMap: Map[String, Map[String, List[TestResult]] = nestedMap.asMap

   println(someMap)
   /*
     Map(
       "A" -> Map("math" -> List(TestResult("A", "math", 75)))
       "B" -> Map(
         "math" -> List(TestResult("B", "math", 80)),
         "bio" -> List(TestResult("B", "bio", 90))
       ),
       "C" -> Map("history" -> List(TestResult("C", "history", 50)))  
     )
    */

Is this doable in scala?

This is doable, I can think of three possible solutions. - 1. Define your own ADT to represent nested maps, it would be very vanilla but will lose some type safety _(similar to how one would define a `Json` data type)_. - 2. Write an **sbt** source generator to implement each overload _(up to some arbitrary number like `22`)_, that way the type safety will be preserved. - 3. use **Shapeless** _(or something similar like **Magnolia** or macros)_ to write a generic version that computes the appropriate type at compile time. — Luis Miguel Mejía Suárez, Apr 10 '23 at 20:33

Dmytro Mitin · Accepted Answer · 2023-04-11T13:06:15.383

You want to return Map[String, Map[String, ... Map[String, List[A]]]]. The type must be known at compile time. So the length of rest: (A => String)* must be known at compile time. You can introduce a type class using Shapeless Sized

// libraryDependencies += "com.chuusai" %% "shapeless" % "2.3.10"
import shapeless.nat.{_0, _2}
import shapeless.{Nat, Sized, Succ}
import scala.collection.Seq // Scala 2.13

// type class
trait AsMap[A, N <: Nat] {
  type Out
  def apply(list: List[A], selectors: Sized[Seq[A => String], N]): Out
}
object AsMap {
  type Aux[A, N <: Nat, Out0] = AsMap[A, N] {type Out = Out0}
  def instance[A, N <: Nat, Out0](f: (List[A], Sized[Seq[A => String], N]) => Out0): Aux[A, N, Out0] = new AsMap[A, N] {
    type Out = Out0
    override def apply(list: List[A], selectors: Sized[Seq[A => String], N]): Out = f(list, selectors)
  }

  implicit def zero[A]: Aux[A, _0, List[A]] = instance((l, _) => l)
  implicit def succ[A, N <: Nat](implicit
    asMap: AsMap[A, N]
  ): Aux[A, Succ[N], Map[String, asMap.Out]] =
    instance((l, sels) => l.groupBy(sels.head).view.mapValues(asMap(_, sels.tail)).toMap)
}

final class NestedStrMap[A, N <: Nat](list: List[A], selectors: (A => String)*){
  def asMap(implicit asMap: AsMap[A, N]): asMap.Out =
    asMap(list, Sized.wrap[Seq[A => String], N](selectors))
}
object NestedStrMap {
  def apply[N <: Nat] = new PartiallyApplied[N]
  class PartiallyApplied[N <: Nat] {
    def apply[A](list: List[A])(selectors: (A => String)*) = new NestedStrMap[A, N](list, selectors: _*)
  }
}

case class TestResult(name: String, testType: String, score: Int)

val testList: List[TestResult] = List(
  TestResult("A", "math", 75),
  TestResult("B", "math", 80),
  TestResult("B", "bio", 90),
  TestResult("C", "history", 50)
)
val nestedMap = NestedStrMap[_2](testList)(_.name, _.testType)
val someMap = nestedMap.asMap
someMap: Map[String, Map[String, List[TestResult]]]
//Map(A -> Map(math -> List(TestResult(A,math,75))), B -> Map(bio -> List(TestResult(B,bio,90)), math -> List(TestResult(B,math,80))), C -> Map(history -> List(TestResult(C,history,50))))

In Scala 2.13, instead of import scala.collection.Seq (i.e. if you want Seq to refer to scala.Seq aka scala.collection.immutable.Seq, which is standard for Scala 2.13, rather than to scala.collection.Seq) then you can define

implicit def immutableSeqAdditiveCollection[T]:
  shapeless.AdditiveCollection[collection.immutable.Seq[T]] = null

(Not sure why this implicit isn't defined, I guess it should.)

Cats auto derived with Seq

If you don't want to specify N manually, you can define a macro

import scala.language.experimental.macros
import scala.reflect.macros.whitebox // libraryDependencies += scalaOrganization.value % "scala-reflect" % scalaVersion.value

object NestedStrMap {
  def apply[A](list: List[A])(selectors: (A => String)*): NestedStrMap[A, _ <: Nat] = macro applyImpl[A]

  def applyImpl[A: c.WeakTypeTag](c: whitebox.Context)(list: c.Tree)(selectors: c.Tree*): c.Tree = {
    import c.universe._
    val A = weakTypeOf[A]
    val len = selectors.length
    q"new NestedStrMap[$A, _root_.shapeless.nat.${TypeName(s"_$len")}]($list, ..$selectors)"
  }
}

// in a different subproject

val nestedMap = NestedStrMap(testList)(_.name, _.testType)
val someMap = nestedMap.asMap
someMap: Map[String, Map[String, List[TestResult]]]
//Map(A -> Map(math -> List(TestResult(A,math,75))), B -> Map(bio -> List(TestResult(B,bio,90)), math -> List(TestResult(B,math,80))), C -> Map(history -> List(TestResult(C,history,50))))

This will not work with

val sels = Seq[TestResult => String](_.name, _.testType)
val nestedMap = NestedStrMap(testList)(sels: _*)

because sels is a runtime value.

Alternatively to Shapeless, you can apply macros from the very beginning (with foldRight/foldLeft as you wanted)

import scala.language.experimental.macros
import scala.reflect.macros.whitebox

final class NestedStrMap[A](list: List[A])(selectors: (A => String)*) {
  def asMap: Any = macro NestedStrMapMacro.asMapImpl[A]
}

object NestedStrMapMacro {
  def asMapImpl[A: c.WeakTypeTag](c: whitebox.Context): c.Tree = {
    import c.universe._

    val A = weakTypeOf[A]
    val ListA = weakTypeOf[List[A]]

    c.prefix.tree match {
      case q"new NestedStrMap[..$_]($list)(..$selectors)" =>
        val func = selectors.foldRight(q"_root_.scala.Predef.identity[$ListA]")((sel, acc) =>
          q"(_: $ListA).groupBy($sel).view.mapValues($acc).toMap"
        )
        q"$func.apply($list)"
    }
  }
}

// in a different subproject

val someMap = new NestedStrMap(testList)(_.name, _.testType).asMap
someMap: Map[String, Map[String, List[TestResult]]]
//Map(A -> Map(math -> List(TestResult(A,math,75))), B -> Map(bio -> List(TestResult(B,bio,90)), math -> List(TestResult(B,math,80))), C -> Map(history -> List(TestResult(C,history,50))))

scala: Nested String Map Builder

1 Answers1