Как написать эту рекурсивную функцию GroupBy в Scala

Question

Недавно я наткнулся на очень полезный GroupBy функции, Groovy сделал доступным на Iterable:

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

Что вы можете использовать для выполнения рекурсивной группеГо на Списки и даже карты see example by mrhaki here

Я хотел бы написать функцию, которая делает то же самое в Scala. Но, только что начав путешествие в Скала, я как бы потерял себя от того, как мне следует определять и применять этот метод. Особенно полезны generics сторона функций и тип возвращаемого значения для этой подписи метода намного выше моего уровня.

Мне нужны более опытные разработчики 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)) 

и получить

Карта (Тилбург -> Карта (март -> Список (liam), Sep -> Список (mrhaki)), New York -> Карта (Мар -> Список (bob)), Амстердам -> Карта (Мар -> Список (kim), май -> Список (britt)))

Answer 2

Я решил добавить еще один ответ из-за совершенно другого подхода.

Вы можете, на самом деле, не обернуть правильно напечатанные карты с огромными обходными решениями. Я не очень хорош в этом, поэтому его можно было бы упростить.

Trick - это создание последовательности типизированных функций, которая в последнее время производит многоуровневую карту с использованием type classes и type path.

Так вот решение

sealed trait KeySeq[-V] { 
    type values 
} 

case class KeyNil[V]() extends KeySeq[V] { 
    type values = Seq[V] 
} 

case class KeyCons[K, V, Next <: KeySeq[V]](f: V => K, next: Next) 
              (implicit ev: RecGroup[V, Next]) extends KeySeq[V] { 
    type values = Map[K, Next#values] 

    def #:[K1](f: V => K1) = new KeyCons[K1, V, KeyCons[K, V, Next]](f, this) 
} 

trait RecGroup[V, KS <: KeySeq[V]] { 
    def group(seq: Seq[V], ks: KS): KS#values 
} 

implicit def groupNil[V]: RecGroup[V, KeyNil[V]] = new RecGroup[V, KeyNil[V]] { 
    def group(seq: Seq[V], ks: KeyNil[V]) = seq 
} 

implicit def groupCons[K, V, Next <: KeySeq[V]](implicit ev: RecGroup[V, Next]): RecGroup[V, KeyCons[K, V, Next]] = 
    new RecGroup[V, KeyCons[K, V, Next]] { 
    def group(seq: Seq[V], ks: KeyCons[K, V, Next]) = seq.groupBy(ks.f) mapValues (_ groupRecursive ks.next) 
    } 



implicit def funcAsKey[K, V](f: V => K): KeyCons[K, V, KeyNil[V]] = 
    new KeyCons[K, V, KeyNil[V]](f, KeyNil[V]()) 

implicit class GroupOps[V](coll: Seq[V]) { 
    def groupRecursive[KS <: KeySeq[V]](ks: KS)(implicit g: RecGroup[V, KS]) = 
    g.group(coll, ks) 
} 

ключевые функции состоят через #: правоассоциативной оператор

так, если мы определим

def mod(m:Int) = (x:Int) => x % m 
def even(x:Int) = x % 2 == 0 

затем

1 to 30 groupRecursive (even _ #: mod(3) #: mod(5)) 

дал бы Map[Boolean,Map[Int,Map[Int,Int]]] !!!

и если из предыдущего вопроса мы хотели бы

users.groupRecursive(((u:User)=> u.city(0)) #: ((u:User) => month(u.birthDate))) 

Мы строим Map[Char,Map[String,User]]!