Блог

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

На самом деле скобки отсутствуют:

 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)
    }
  

Вся слава автору этого кода.