Блог

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

 def find[A,B](aList: List[A], bList: List[B]): Set[(A,B)] = {
  def findHelper[A,B](aList: List[A], bList: List[B], acc: Set[(A,B)]): Set[(A,B)] = {
    (aList, bList) match {
      case (head1 :: tail1, head2::tail2) => {
        findHelper[A, B](tail1, tail2, acc    Set((head1, head2)))
      }
      case (List(), head2::tail2) => acc
      case (List(), List()) => acc
    }
  }
  findHelper(aList, bList, Set())
}
println(find(List(1,2,3,4,5), List(7,8,9,10,11)))
 

В результате я получаю только «нравится (1,7), (2,8) » и т. Д.
Я, очевидно, знаю, почему, но я не знаю, как сочетать каждую пару с собой. Я не знаю, что делать, когда мой первый список опустеет после :: операции.

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

Вот один из способов сделать это.

 def cartPrd[A,B](aList: List[A], bList: List[B]): Set[(A,B)] = {
  def getAs(as: List[A]): List[(A,B)] = as match {
    case Nil => Nil
    case hd::tl => getBs(hd, bList)    getAs(tl)
  }
  def getBs(a: A, bs: List[B]): List[(A,B)] = bs match {
    case Nil => Nil
    case hd::tl => (a,hd) :: getBs(a,tl)
  }
  getAs(aList).toSet
}

cartPrd(List(1,2,1), List('A','B','B'))
//res0: Set[(Int, Char)] = Set((1,A), (1,B), (2,A), (2,B))
 

Все это намного проще при простом for понимании.

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

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

Что означает эта строка? «случай (остается @ (a :: ), b :: tailB)» Я имею в виду, что делают «@» и (a :: _)?

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

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

И вы, вероятно, сделали то, что мне было нужно: остаются ли значения и как разные значения, и вы просто сохраняете полный список в значении as/bs, а когда он становится пустым, вы просто снова используете полный список? Например, здесь: «case ( :: tailA, ноль) => цикл(remainingAs = tailA, remainingBs = 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.