通过模式匹配的笛卡尔积

Question

我是一名大学生，正在学习 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) 等。我显然知道为什么，但我不知道如何将每一对与自身结合起来。当我的第一个列表在 :: 操作后变空时，我不知道该怎么办。

Answer 1

如评论中所述，只需要遍历一个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 理解，这一切都变得容易多了。

Answer 2

如评论中所述，问题是您同时迭代两个列表，而您需要为第一个列表的每个元素迭代第二个列表一次。

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

What does that line mean? " case (remainingAs @ (a :: ), b :: tailB) " I mean, what does "@" and (a :: _) do?

语法 case foo @ bar 意味着如果你的模式匹配匹配模式 bar 然后将它分配给新变量 foo.

所以，在这种情况下，我是说如果 as 的列表不为空 （即是一个 cons ::） 然后把它的头作为一个新的变量 a 和整个列表作为一个新变量 remainingAs。请注意，在这种情况下，根本不需要它，因为我可以只使用前面的 remainingAs 进行模式匹配，它也包含整个列表；我个人喜欢定义我将在 case 部分中使用的所有变量，但您可以只使用 case ((a :: _), b :: tailB)，代码将按预期编译和工作。

And you probably did which I needed: are remainingAs and as different values, and you just keep the full List in as/bs value and when it gets empty, you just again use the full one? For example here: "case ( :: tailA, Nil) => loop(remainingAs = tailA, remainingBs = bs, acc)"

我不太确定我是否理解你在说什么，但你是对的，我记录了最初的第二个列表，这样当我用完它时我可以从头开始。

因此，如您所见，代码包含三种情况，可以大致理解为：

当第一个列表不为空时，取其头部。
然后迭代第二个列表，取其头部并将两个头部的一对添加到集合中，并继续处理第二个列表的尾部。
当您到达第二个列表的尾部时，然后从第一个列表的尾部重新开始，并将第二个列表重新启动到其原始形式。
继续该过程，直到第一个列表为空，此时 return 当前累加器。

注：我个人认为有两个递归函数的版本更容易理解。因为这看起来更像是两个循环，第二个循环嵌套在第一个循环中，这就是您在命令式语言中所做的。

其他解决方案包括：

两个递归函数：

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中看到代码运行。

通过模式匹配的笛卡尔积

Cartesian product by pattern matching

scala

pattern-matching

cartesian