Scala: перекрестное (декартово) произведение с несколькими источниками и разнородными типами

Я пытаюсь построить несколько перекрестных произведений обходов разных (но каждый однородных) типов. Желаемый возвращаемый тип — это обход кортежа с типом, соответствующим типам во входных обходах. Например:

List(1, 2, 3) cross Seq("a", "b") cross Set(0.5, 7.3)

Это должно дать Traversable[(Int, String, Double)] со всеми возможными комбинациями из трех источников. Случай объединения только двух источников был хорошо рассмотрен здесь. Данная идея такова:

implicit class Crossable[X](xs: Traversable[X]) {
  def cross[A](ys: Traversable[A]) = for { x <- xs; y <- ys } yield (x, y)
}

В комментариях кратко упоминается проблема большего количества источников, но я ищу решение, которое не зависит ни от shapeless, ни от scalaz (с другой стороны, я не против иметь какой-то шаблон для масштабирования до Tuple22). Я хотел бы сделать что-то вроде следующего:

implicit class Crossable[X](xs: Traversable[X]) {
  def cross[A](ys: Traversable[A]) = for { x <- xs; y <- ys } yield (x, y)
  def cross[A,B](ys: Traversable[(A,B)]) = // ... extend all Tuple2's in ys with x in xs to Tuple3's
  def cross[A,B,C](ys: Traversable[(A,B,C)]) = // ...
  // ...
}

Очевидно, что это не работает из-за стирания типа (и, к сожалению, вероятно, потребуется использовать круглые скобки в приведенном выше примере, потому что cross будет правильным ассоциативным).

Мой вопрос: возможно ли как-то использовать функции отражения Scala 2.10 для решения проблемы? В общем, сопоставление A и X с различными типами кортежей (и параметрами их типов, что кажется сложной задачей) и объединение их с более крупными кортежами должно обеспечить решение, удовлетворяющее ассоциативному закону, верно?


reflection scala cartesian-product type-erasure cross-product
person bluenote10    schedule 25.04.2013    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Я попробовал и придумал следующее:

trait Crosser[A,B,C] {
  def cross( as: Traversable[A], bs: Traversable[B] ): Traversable[C]
}

trait LowPriorityCrosserImplicits {
  private type T[X] = Traversable[X]

  implicit def crosser2[A,B] = new Crosser[A,B,(A,B)] {
    def cross( as: T[A], bs: T[B] ): T[(A,B)] = for { a <- as; b <- bs } yield (a, b)
  }
}

object Crosser extends LowPriorityCrosserImplicits {
  private type T[X] = Traversable[X]

  implicit def crosser3[A,B,C] = new Crosser[(A,B),C,(A,B,C)] {
    def cross( abs: T[(A,B)], cs: T[C] ): T[(A,B,C)] = for { (a,b) <- abs; c <- cs } yield (a, b, c)
  }

  implicit def crosser4[A,B,C,D] = new Crosser[(A,B,C),D,(A,B,C,D)] {
    def cross( abcs: T[(A,B,C)], ds: T[D] ): T[(A,B,C,D)] = for { (a,b,c) <- abcs; d <- ds } yield (a, b, c, d)
  }

  // and so on ...
}

implicit class Crossable[A](xs: Traversable[A]) {
  def cross[B,C](ys: Traversable[B])(implicit crosser: Crosser[A,B,C]): Traversable[C] = crosser.cross( xs, ys )
}

Основная идея состоит в том, чтобы передать работу классу типов (Crosser) и реализовать все различные арности, просто специализируясь на Traversables кортежей с соответствующей арностью минус единица. Некоторые тесты в REPL:

scala> List(1, 2, 3) cross Seq("a", "b") cross Set(0.5, 7.3)
res10: Traversable[(Int, String, Double)] = List((1,a,0.5), (1,a,7.3), (1,b,0.5), (1,b,7.3), (2,a,0.5), (2,a,7.3), (2,b,0.5), (2,b,7.3), (3,a,0.5), (3,a,7.3), (3,b,0.5), (3,b,7.3))
person Régis Jean-Gilles    schedule 25.04.2013
comment
Вау, это довольно круто! Большое спасибо! Добавление правильных ассоциативных версий также кажется простым при таком подходе. Я заметил, что вы избавились от двусмысленных неявных ошибок компилятора, введя crosser2 в признак (который в противном случае всегда совпадал бы). Я предполагаю, что должно быть какое-то правило приоритета, зависящее от иерархии классов, для неявных? Что меня все еще озадачивает: почему crosser2, crosser3, ... на самом деле находятся в области видимости? Я ожидал, что мне придется import Crosser._ привести их в соответствие, но, похоже, это не так. - person bluenote10; 26.04.2013
comment
На случай, если кто-то еще захочет использовать это: я только что написал небольшой генератор кода (когда-нибудь я выучу макросы) и загрузил Gist, содержащий весь шаблон до достаточно высокого уровня (начиная с 19-го параметра типа, я получил странные ошибки компилятора, но 18 должно быть более чем достаточно для меня). - person bluenote10; 26.04.2013
comment
Причина, по которой вам не нужно делать import Crosser._, заключается в том, что Crosser неявно передается в Crossable.cross, а правила неявного разрешения говорят, что при поиске неявного значения типа T компилятор автоматически просматривает члены сопутствующего объекта. из T (если есть). См. SLS 7.2. - person Régis Jean-Gilles; 26.04.2013