sorting - 在 Haskell 中解释这个 'Merge' 函数

Question

我正在学习 Haskell，但无法理解此功能。我正在实现合并排序。我实现了合并排序递归函数，但我不明白这个“合并”函数在做什么。我理解命令式语言中的合并排序，但我不理解这里的语法。

merge []         ys                   = ys
merge xs         []                   = xs
merge xs@(x:xt) ys@(y:yt) | x <= y    = x : merge xt ys
                          | otherwise = y : merge xs yt

Answer 1

merge []         ys                   = ys

如果第一个参数为空，则给出第二个参数。

merge xs         []                   = xs

如果第二个参数为空，则给出第一个参数。

merge xs@(x:xt) ys@(y:yt) | x <= y    = x : merge xt ys
                          | otherwise = y : merge xs yt

如果 x小于或等于 y , cons (添加到前面) x 到合并 xs 其余部分的结果(即 xt )和 ys .否则 y更小，因此将其与 xs 与 ys 的其余部分合并的结果相结合(即 yt )。
xs@(x:xt)是使用“占位符”的参数解构。结果是 xs将引用整个第一个参数，而 x是头和xt是尾部。

由于合并是递归定义的，它将继续从 xs 和 ys 中提取元素，直到至少有一个为空，然后简单地返回它。

条 (|) 表示 "guards" ，它可以让您以简洁明了的方式定义条件。