Почему cons не является членом immutable.this.IndexedSeq [List [List [scala .this.Tuple2 [scala .this.Char, scala .this.Int]]]] curr :: result

Question

Учитывая список кортежей формы (Char, Int), я хочу найти подмножества списка, например, если мой список был

List(('a', 2), ('b', 2))

Тогда моя функция должна вернуть

List(
  List(),
  List(('a', 1)),
  List(('a', 2)),
  List(('b', 1)),
  List(('a', 1), ('b', 1)),
  List(('a', 2), ('b', 1)),
  List(('b', 2)),
  List(('a', 1), ('b', 2)),
  List(('a', 2), ('b', 2))
)

Я написал эту функцию

def combinations(occurrences: List[(Char,Int)]): List[List[(Char,Int)]] = {
  val curr = occurrences filter { case (c,o) => o != 0}
  if (curr.isEmpty) List(List())
  else {
    val result = for{
      i <- 0 until occurrences.length
    } yield combinations(occurrences.updated(i,(occurrences(i)._1,occurrences(i)._2 - 1)))
    curr :: result
  }
}

Но я продолжаю получать следующую ошибку, и я понятия не имею, почему вид cons должен быть членом List [List [(Char, Int)] ]. Любая помощь будет принята с благодарностью.

ScalaFiddle.scala:8: error: value :: is not a member of immutable.this.IndexedSeq[List[List[scala.this.Tuple2[scala.this.Char,scala.this.Int]]]]
  curr :: result
       ^

Я изменил свой код на следующий

def combinations(occurrences: List[(Char,Int)]): List[List[(Char,Int)]]      = {
  val curr = occurrences filter { case (c,o) => o != 0}
  if (curr.isEmpty) List(List())
  else {
    val result = for{
     (c,o) <- curr
    } yield combinations(occurrences.updated(curr.indexOf((c,o)),(c,o-1)))
    curr :: result
  }
}

, но теперь я получаю следующую ошибку

error: type mismatch;
 found   : immutable.this.List[immutable.this.List[scala.this.Product    with scala.this.Serializable{}]]
 required:    List[List[scala.this.Tuple2[scala.this.Char,scala.this.Int]]]
  curr :: result 

Answer 1

Короткий ответ: поскольку 0 until occurrences.length - это Range[Int], result не List, а IndexedSeq, на котором :: недоступен.

for {
  i <- 0 until occurrences.length
} yield f(i)

обесценивается компилятором в

(0 until occurrences.length).map(i => f(i))

, а затем в

Range(0, occurrences.length + 1).map(i => f(i))

map на Range наследуется от IndexedSeq, поэтому имеет подпись (в 2.13 по крайней мере):

def map[B](f: (Int) => B): IndexedSeq[B]

Итак, общий тип результата - IndexedSeq[List[List[(Char, Int)]]]. Этот результат можно преобразовать в List с помощью toList.

curr :: (result.toList)

Answer 2

Как упоминалось в моем комментарии (выше), я нашел несколько разных способов разрешения конфликта типов, но не таким образом, чтобы получить желаемые результаты.

def combinations(occurrences: List[(Char,Int)]): List[List[(Char,Int)]] = {
  val curr = occurrences filter { case (c,o) => o != 0 }
  if (curr.isEmpty) List(List())
  else {
    val result = for {
      (c, o) <- curr
      res <- combinations(curr.updated(curr.indexOf((c, o)), (c, o-1)))
// using occurrences here ^^^^ tends to StackOverflow
    } yield res
    curr :: result
  }
}

def combinations(occurrences: List[(Char,Int)]): List[List[(Char,Int)]] = {
  val curr = occurrences filter { case (c,o) => o != 0 }
  if (curr.isEmpty)
    List(List()) // or Nil for a different wrong result
  else {
    val result = curr.flatMap { case (c, o) =>
      combinations(curr.updated(curr.indexOf((c, o)), (c, o-1)))
    }
    curr :: result
  }
}

Вот другой подход (который, кажется, действительно работает).

def crossProd[T](in: Seq[T]*): Seq[Seq[T]] =
  if (in.isEmpty) in
  else in.tail.foldLeft(in.head.map(Seq(_))) {
    for {sentence <- _; word <- _} yield sentence :+ word
  }

def combinations(occurrences: List[(Char,Int)]) : List[List[(Char,Int)]] =
  crossProd(occurrences.map{case (c,n) => (0 to n).map(x => (c,x))}:_*)
    .map(_.filter(_._2 > 0).toList)
    .toList

тестирование:

combinations(List(('c',2),('x',3),('#',1)))
//res0: List[List[(Char, Int)]] = 
// List(List()
// , List((#,1))
// , List((x,1))
// , List((x,1), (#,1))
// , List((x,2))
// , List((x,2), (#,1))
// , List((x,3))
// , List((x,3), (#,1))
// , List((c,1))
// , List((c,1), (#,1))
// , List((c,1), (x,1))
// , List((c,1), (x,1), (#,1))
// , List((c,1), (x,2))
// , List((c,1), (x,2), (#,1))
// , List((c,1), (x,3))
// , List((c,1), (x,3), (#,1))
// , List((c,2))
// , List((c,2), (#,1))
// , List((c,2), (x,1))
// , List((c,2), (x,1), (#,1))
// , List((c,2), (x,2))
// , List((c,2), (x,2), (#,1))
// , List((c,2), (x,3))
// , List((c,2), (x,3), (#,1)))