快速排序在 APL 中的解释

Question

我试图理解APL中的经典快速排序算法：

Q←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵⌷⍨?≢⍵}

有一些我不理解的事情，还有一些我不喜欢的风格选择，所以我要列出所有这些问题。希望有人能够解释一下。

1. 我知道在 { } defn 内部，⍺ 是左参数，⍵ 是右参数。在 S←{⍺⌿⍨⍺ ⍺⍺ ⍵} 中，⍺⍺ 是什么？同样地，是否存在一个 ⍵⍵？S 中的 ⍺ 是指 S 的左参数 还是 Q 的左参数？

我猜测 S 中的 ⍺ 指的是 S 的左参数。而 ⍺⍺ 指的是 封闭函数（即 Q 的 ⍺）的 ⍺。

为什么要频繁使用 commute (⍨)？代码不是更清晰，写成这样吗：

Q←{1≥≢⍵:⍵ ⋄ S←{(⍺ ⍺⍺ ⍵)⌿⍺} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵[?≢⍵]}

我能想到使用 commute 的唯一用途是减少使用括号 () 和 []，但这似乎不值得为了简洁而损失可读性。我是否在 "APL way" 上漏掉了什么？

3. 这实际上并没有执行快速排序，是吗？快速排序被定义为原地排序。然而，我对APL语义的理解是，这段代码实际上在递归子调用中构建新数组，然后使用⍪将它们连接起来。事实上，这也是针对Haskell快速排序提出的批评。在APL语义中，有什么东西告诉我们这个操作是“原地”完成的吗？请注意，我对“足够聪明的编译器”论点不感兴趣，因为数组分析基本上是具有挑战性的。如果APL编译器确实将其转换为原地算法，我将非常珍视关于它如何进行此分析的详细信息——这是相当了不起的成就！

4. 为什么要使用≢⍵来查找维度大小？为什么不使用⍴⍵？通常，我发现人们在查询沿最外层维度的大小时会使用≢而不是⍴，即使该函数仅在一维情况下有效。再次说明，我认为我可能没有理解APL的方式。

非常感谢。

- Siddharth Bhat

Answer 1

在 { } defn 中，⍺ 代表左侧参数，⍵ 代表右侧参数。在 S←{⍺⌿⍨⍺ ⍺⍺ ⍵} 中，⍺⍺ 代表左操作数，类似的，是否有 ⍵⍵ 呢？

S←{⍺⌿⍨⍺ ⍺⍺ ⍵} 被称为 dop。类似于 dfn 是用户定义函数一样，dop 是用户定义运算符，其行为类似于 ¨、⍨ 或 ∘。

语义总结：

• 如果 dop 只提到了 ⍺⍺ （没有 ⍵⍵），则它将成为一个单参运算符，您可以使用 x (m S) y 来调用。
• 如果 dop 提到了 ⍵⍵，则它将成为一个双参运算符，您可以使用 x (m S n) y 来调用。
• 在两种情况下，⍺⍺（其值为 m）和 ⍵⍵（其值为 n）都可以是一个数组或一个函数。
• 您还可以决定在 dop 的主体中不使用 ⍺，此时您可以将其视为省略了左侧参数的调用，即(m S) y 或 (m S n) y。
• m 被称为左操作数，n 被称为右操作数。它们与左参数(x)和右参数(y)不同。

在您的示例中，S 只提到了 ⍺⍺，因此它将作为 x (m S) y 调用。如果您像这样调用 S：1 2 3 >S 2，则将计算出一个单个的 3。

在S的主体内，由⍺和⍵字符组成的所有内容都是指对S的参数/操作数。原始的Q参数是不可见的（除非它们首先被分配给一个变量，在这种情况下，它们可见作为变量名）。

2. 为什么要大量使用逆置运算符 (⍨)？

我认为这主要是一种风格选择。我也更喜欢写带括号的代码而不是将其用于生产代码，除非使用方式很容易识别为APL语言习惯。例如，我会写3÷⍨whatever而不是 (whatever)÷3来进行常数除法。

3. 这实际上并没有执行快速排序，对吗？

你是正确的。如你已经提到的，快速排序被设计为原地排序才能真正称为Quick（商标）。APL可以进行内存预分配和数组共享以减少一些内存复制和分配，但至少在创建三个子数组（具有小于/等于/大于枢轴的元素）并稍后连接时一些复制是不可避免的。

需要注意的一点是，与Haskell不同，APL确实具有原地赋值，它的写法类似于x[i]←v。如果要在APL中正确实现快速排序，必须像C语言一样编写代码（传递索引给递归调用等）。

4. 为什么要使用≢⍵来查找维度大小？而不是使用⍴⍵？

≢称为“tally”，而 ⍴ 称为“shape”。≢始终返回一个标量值，而⍴返回一个向量（如果给定向量参数，则其将是一个长度为1的向量）。虽然标量和长度为1的向量在大多数场景中表现相同，但它们是不同的东西，例如，1≡,1为false。

我认为有区分这两者的好习惯，并尽可能选择标量而不是长度为1的向量，是一个好习惯。一个值得注意的例外是当您需要显式封闭数组时（标量无法封闭）。

- Bubbler