scala - 对归并排序的实现感到困惑

Question

这一行发生了什么，x 被连接到 xs1 但 x 和 xs1 不是在任何地方定义？

case (x :: xs1, y :: ys1) =>

同样在这里，下面的x和y有什么值(value)？合并是否作为案例类的一部分被递归调用？

if( x < y) x :: merge(xs1 , ys)

这是完整的 Scala 代码:

object mergesort {

    def msort(xs: List[Int]): List[Int] = {
        val n = xs.length / 2
        if(n == 0) xs
        else {
            def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs , ys) match {
            case (Nil, ys) => ys
            case (xs, Nil) => xs
            case (x :: xs1, y :: ys1) =>
                if( x < y) x :: merge(xs1 , ys)
                else y :: merge(xs, ys1)
            }


        val (fst, snd) = xs splitAt n
        merge(msort(fst), msort(snd))
        }
    }                                         //> msort: (xs: List[Int])List[Int]

    val nums = List(2, -4, 5, 7, 1)           //> nums  : List[Int] = List(2, -4, 5, 7, 1)
    msort(nums)                               //> res0: List[Int] = List(-4, 1, 2, 5, 7)

}

Answer 1

在

case (x :: xs1, y :: ys1) =>  

:: 是模式匹配中的语法糖，用于将 list 解构为 head 和 tail

列表 xs 被解构为头部 x 和尾部 xs。

在模式匹配中，:: 解构一个列表，与它在正常情况下实际做的完全相反，构造 一个列表。

阅读 The Point of Pattern Matching in Scala 中的解构对象