Несоответствие типа для понимания: получение продукта с помощью Serializable

Я пишу функцию, которая будет принимать список вхождений символов (List[(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))
)

Я реализовал это так:

type Occurrences = List[(Char, Int)]

def combinations(occurrences: Occurrences): List[Occurrences] =
  if (occurrences.isEmpty) List(List())
  else for {
    (c, n) <- occurrences
    i <- n to 1 by -1
  } yield (c, i) :: combinations(occurrences.tail)

И я получаю такую ​​ошибку:

type mismatch;
 found   : List[List[Product with Serializable]]
 required: List[Occurrences]
    (which expands to)  List[List[(Char, Int)]]

Пожалуйста, помогите мне понять, почему это происходит и как это исправить?

Я пробовал переписать его как flatMap ..., используя Intellij "Explain Scala code" и т. Д.


types scala yield for-comprehension
person Alex V.    schedule 20.10.2016    source источник
comment
Есть какая-то конкретная причина, по которой вы не можете принять ответ?   -  person tkachuko    schedule 20.10.2016

Ответы (1)


arrow_upward
4
arrow_downward

Собственно скобки отсутствуют:

type Occurrences = List[(Char, Int)]

  def combinations(occurrences: Occurrences): List[Occurrences] =
    if (occurrences.isEmpty) List(List())
    else (for {
      (c, n) <- occurrences
      i <- n to 1 by -1
    } yield (c, i)) :: combinations(occurrences.tail)

В исходном коде для понимания вы пытались получить (c, i) :: combinations(occurrences.tail), который является List с элементом Any внутри (Tuple / другой List).

ОБНОВЛЕНИЕ:

Правильный метод, требующий магии:

type Occurrences = List[(Char, Int)]


  /**
    * Returns the list of all subsets of the occurrence list.
    *  This includes the occurrence itself, i.e. `List(('k', 1), ('o', 1))`
    *  is a subset of `List(('k', 1), ('o', 1))`.
    *  It also include the empty subset `List()`.
    *
    *  Example: the subsets of the occurrence list `List(('a', 2), ('b', 2))` are:
    *
    *    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))
    *    )
    *
    *  Note that the order of the occurrence list subsets does not matter -- the subsets
    *  in the example above could have been displayed in some other order.
    */
  def combinations(occurrences: Occurrences): List[Occurrences] =
    occurrences.foldRight(List[Occurrences](Nil)) {
      case ((ltr, cnt), acc) =>
        acc ::: (for {
          comb <- acc
          ltrNum <- 1 to cnt
        } yield (ltr, ltrNum) :: comb)
    }

Слава автору этого кода.

person tkachuko    schedule 20.10.2016
comment
Круглые скобки определяют тип, но меняют предполагаемое поведение кода. Я пытаюсь сдать ровно (c, i) :: combinations(occurrences.tail) - person Alex V.; 20.10.2016
comment
Давайте разберемся: combinations(occurrences.tail) имеет тип List[List[(Char, Int)]]. Вы пытаетесь добавить (c, i), который равен (Char, Int). Вы должны добавить List[(Char, Int)] - person tkachuko; 20.10.2016
comment
Однако даже после этого он не дает требуемого результата, что заставляет меня думать, что сам алгоритм не совсем правильный. Я не собираюсь публиковать решение алгоритмической проблемы, поскольку ваш вопрос требует решения проблемы компиляции. - person tkachuko; 20.10.2016
comment
Пожалуйста, посмотрите обновление, оно содержит метод, который делает то, что вам нужно. - person tkachuko; 20.10.2016