Есть два решения.Первый заключается в том, чтобы не требовать, чтобы контейнеры были подклассом какого-то общего суперкласса, но чтобы их можно было преобразовать в один (используя неявные аргументы функции).Если контейнер уже является подклассом требуемого типа, существует предопределенное преобразование идентификатора, которое только возвращает его.
import collection.mutable.Builder
import collection.TraversableLike
import collection.generic.CanBuildFrom
import collection.mutable.SeqLike
class Cartesian[T, ST[T], TT[S]](val ll: TT[ST[T]])(implicit cbf: CanBuildFrom[Nothing, T, ST[T]], seqLike: ST[T] => SeqLike[T, ST[T]], traversableLike: TT[ST[T]] => TraversableLike[ST[T], TT[ST[T]]] ) extends Iterator[ST[T]] {
def combicount (): Int = (1 /: ll) (_ * _.length)
val last = combicount - 1
var iter = 0
override def hasNext (): Boolean = iter < last
override def next (): ST[T] = {
val res = combination (ll, iter, cbf())
iter += 1
res
}
def combination (xx: TT[ST[T]], i: Int, builder: Builder[T, ST[T]]): ST[T] =
if (xx.isEmpty) builder.result
else combination (xx.tail, i / xx.head.length, builder += xx.head (i % xx.head.length) )
}
Такого рода работы:
scala> new Cartesian[String, Vector, Vector](Vector(Vector("a"), Vector("xy"), Vector("AB")))
res0: Cartesian[String,Vector,Vector] = empty iterator
scala> new Cartesian[String, Array, Array](Array(Array("a"), Array("xy"), Array("AB")))
res1: Cartesian[String,Array,Array] = empty iterator
Мне нужно было явно передать типы из-за ошибки https://issues.scala -lang.org / browse / SI-3343
Следует отметить, что это лучше, чем использование экзистенциальных типов, потому что при вызове next в итераторе возвращается правильный тип, а не Seq [Any].
Есть несколько недостатков.здесь:
- Если контейнер не является подклассом требуемого типа, он преобразуется в тот, который стоит по производительности
- Алгоритм не является полностью универсальным.Нам необходимо преобразовать типы в SeqLike или TraversableLike только для того, чтобы использовать подмножество функций, предлагаемых этими типами.Так что сделать функцию преобразования может быть сложно.
- Что если некоторые возможности могут интерпретироваться по-разному в разных контекстах?Например, у прямоугольника есть два свойства длины (ширина и высота)
Теперь для альтернативного решения.Мы отмечаем, что на самом деле нас не интересуют типы коллекций, только их возможности:
- TT должен иметь
foldLeft, get(i: Int) (чтобы получить голову / хвост) - ST должен иметь
length, get(i: Int) и Builder
Таким образом, мы можем закодировать их:
trait HasGet[T, CC[_]] {
def get(cc: CC[T], i: Int): T
}
object HasGet {
implicit def seqLikeHasGet[T, CC[X] <: SeqLike[X, _]] = new HasGet[T, CC] {
def get(cc: CC[T], i: Int): T = cc(i)
}
implicit def arrayHasGet[T] = new HasGet[T, Array] {
def get(cc: Array[T], i: Int): T = cc(i)
}
}
trait HasLength[CC] {
def length(cc: CC): Int
}
object HasLength {
implicit def seqLikeHasLength[CC <: SeqLike[_, _]] = new HasLength[CC] {
def length(cc: CC) = cc.length
}
implicit def arrayHasLength[T] = new HasLength[Array[T]] {
def length(cc: Array[T]) = cc.length
}
}
trait HasFold[T, CC[_]] {
def foldLeft[A](cc: CC[T], zero: A)(op: (A, T) => A): A
}
object HasFold {
implicit def seqLikeHasFold[T, CC[X] <: SeqLike[X, _]] = new HasFold[T, CC] {
def foldLeft[A](cc: CC[T], zero: A)(op: (A, T) => A): A = cc.foldLeft(zero)(op)
}
implicit def arrayHasFold[T] = new HasFold[T, Array] {
def foldLeft[A](cc: Array[T], zero: A)(op: (A, T) => A): A = {
var i = 0
var result = zero
while (i < cc.length) {
result = op(result, cc(i))
i += 1
}
result
}
}
}
(строго говоря, HasFold не требуется, так как его реализацияс точки зрения длины и получения, но я добавил это здесь, чтобы алгоритм был переведен более четко)
Теперь алгоритм:
class Cartesian[T, ST[_], TT[Y]](val ll: TT[ST[T]])(implicit cbf: CanBuildFrom[Nothing, T, ST[T]], stHasLength: HasLength[ST[T]], stHasGet: HasGet[T, ST], ttHasFold: HasFold[ST[T], TT], ttHasGet: HasGet[ST[T], TT], ttHasLength: HasLength[TT[ST[T]]]) extends Iterator[ST[T]] {
def combicount (): Int = ttHasFold.foldLeft(ll, 1)((a,l) => a * stHasLength.length(l))
val last = combicount - 1
var iter = 0
override def hasNext (): Boolean = iter < last
override def next (): ST[T] = {
val res = combination (ll, 0, iter, cbf())
iter += 1
res
}
def combination (xx: TT[ST[T]], j: Int, i: Int, builder: Builder[T, ST[T]]): ST[T] =
if (ttHasLength.length(xx) == j) builder.result
else {
val head = ttHasGet.get(xx, j)
val headLength = stHasLength.length(head)
combination (xx, j + 1, i / headLength, builder += stHasGet.get(head, (i % headLength) ))
}
}
И использовать:
scala> new Cartesian[String, Vector, List](List(Vector("a"), Vector("xy"), Vector("AB")))
res6: Cartesian[String,Vector,List] = empty iterator
scala> new Cartesian[String, Array, Array](Array(Array("a"), Array("xy"), Array("AB")))
res7: Cartesian[String,Array,Array] = empty iterator
Вероятно, в Scalaz все это предопределено для вас, к сожалению, я не очень хорошо это знаю.
(опять же, мне нужно передать типы, потому что логический вывод не дает правильного вида)
Преимущество заключается в том, что алгоритм теперь полностью универсален и нет необходимости в неявных преобразованиях из Array в WrappedArray, чтобы он работал
Упражнение: определение для кортежей; -)