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

Как упоминалось в комментариях, проблема заключается в том, что вы выполняете итерацию обоих списков одновременно, тогда как вам нужно повторять второй список один раз для каждого элемента первого.

def cartesianProduct[A, B](as: List[A], bs: List[B]): Set[(A, B)] = {
  @annotation.tailrec
  def loop(remainingAs: List[A], remainingBs: List[B], acc: Set[(A, B)]): Set[(A, B)] =
    (remainingAs, remainingBs) match {      
      case (remainingAs @ (a :: _), b :: tailB) =>
        loop(remainingAs, remainingBs = tailB, acc + (a -> b))
      
      case (_ :: tailA, Nil) =>
        loop(remainingAs = tailA, remainingBs = bs, acc)
      
      case (Nil, _) =>
        acc
    }
  
  loop(remainingAs = as, remainingBs = bs, acc = Set.empty)
}

Что означает эта строка? case (остальные As @(a::), b::tailB) Я имею в виду, что делает @ и (a::_)?

Синтаксис case foo @ bar означает, что если то, что соответствует вашему шаблону, соответствует шаблону bar, назначьте его новой переменной foo.

Итак, в этом случае я говорю, что если список as не пуст (т. е. является минусом ::), тогда возьмите его заголовок как новую переменную a и весь список как новую переменную remainingAs. Обратите внимание, что в данном случае это было вообще не нужно, так как я мог бы просто использовать предыдущий remainingAs, на котором мы сопоставляем шаблон, который также содержит весь список; Лично мне нравится определять все переменные, которые я собираюсь использовать в части case, но вы можете просто использовать case ((a :: _), b :: tailB), и код будет компилироваться и работать, как и ожидалось.

И вы, вероятно, сделали то, что мне было нужно: оставшиеся As и as разные значения, и вы просто сохраняете полный список в значении as/bs, а когда он становится пустым, вы просто снова используете полный? Например здесь: case(::tailA,Nil)=›loop(оставшиесяAs=tailA,оставшиесяBs=bs,acc)

Я не совсем уверен, понимаю ли я, что вы говорите, но вы правы в том, что я отслеживаю исходные вторые списки, чтобы, когда я их исчерпаю, я мог начать все сначала.

Итак, как вы можете видеть, код имеет три случая и может быть прочитан примерно так:

1. Пока первый список не пуст, займитесь его головой.
2. Затем повторите второй список, взяв его голову и добавив пару обеих головок в набор, и продолжите процесс с хвостом второго списка.
3. Когда вы дойдете до хвоста второго списка, снова начните с хвоста первого списка и перезапустите второй список до его исходной формы.
4. Продолжайте процесс, пока первый список не станет пустым, в этот момент верните текущий аккумулятор.

Примечание. Я лично считаю, что версию с двумя рекурсивными функциями легче понять. Поскольку это больше похоже на два цикла со вторым, вложенным в первый, что вы бы сделали в императивном языке.

Другие решения включают в себя:

Две рекурсивные функции:

def cartesianProduct[A, B](as: List[A], bs: List[B]): Set[(A, B)] = {  
  @annotation.tailrec
  def outerLoop(remaining: List[A], acc: Set[(A, B)]): Set[(A, B)] =
    remaining match {
      case a :: tail =>
        @annotation.tailrec
        def innerLoop(remaining: List[B], acc: Set[(A, B)]): Set[(A, B)] =
          remaining match {
            case b :: tail =>
              innerLoop(remaining = tail, acc + (a -> b))
            
            case Nil =>
              acc
          }
      
        val newAcc = innerLoop(remaining = bs, acc)
        outerLoop(remaining = tail, newAcc)
      
      case Nil =>
        acc
    }

  outerLoop(remaining = as, acc = Set.empty)
}

Или функции более высокого порядка:
(вы также можете написать это, используя синтаксис for)

def cartesianProduct[A, B](as: List[A], bs: List[B]): Set[(A, B)] =
  as.iterator.flatMap { a =>
    bs.iterator.map { b =>
      a -> b
    }
  }.toSet

Вы можете увидеть работающий код в Scastie.