APL中quicksort的解释
Explanation of quicksort in APL
我正在尝试理解 APL 中的经典快速排序：
Q←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵⌷⍨?≢⍵}
有些东西我不明白，有些文体选择困扰我，所以我要把它们都列出来。我希望有人能给我解释一下。
- 我理解在
{ }定义中，⍺是左参数，⍵是右参数。 S←{⍺⌿⍨⍺ ⍺⍺ ⍵}中的⍺⍺是什么？同样，有没有⍵⍵？ S里面的⍺是指S的left参数还是Q的left参数？
我的猜测是S里面的⍺指的是S的左参数。 ⍺⍺指的是封闭函数的⍺（即Q的⍺）。
- 为什么大量使用通勤 (
⍨)？代码不是更清楚地写成：
Q←{1≥≢⍵:⍵ ⋄ S←{(⍺ ⍺⍺ ⍵)⌿⍺} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵[?≢⍵]}
我能想到的使用 commute 的唯一用途是减少括号 () 和 [] 的使用，但这似乎不值得牺牲易读性。我在这里遗漏了 "APL way" 的某些内容吗？
这实际上不是在执行快速排序，是吗？快速排序被定义为就地。然而，我对 APL 语义的理解是，这段代码实际上 在递归子调用上构建新数组 ，并使用 ⍪ 连接它们。的确，这就是same criticism that is levelled at Haskell's quicksort。我在 APL 语义中是否遗漏了一些信息来通知此操作已完成 "in-place"？请注意，我对 "sufficiently smart compiler" 参数不感兴趣，因为数组分析从根本上讲具有挑战性。如果 APL 编译器 确实将其转换为就地算法 ，我将非常重视有关它如何设法执行此分析的详细信息 --- 这是一项了不起的成就！
为什么要用≢⍵求维度大小？为什么不 ⍴⍵？一般来说，我发现人们使用 ≢ 而不是 ⍴ 来查询最外层维度的大小， 即使函数工作的唯一情况是一维 .同样，我认为我缺少 APL 方式中的某些内容。
非常感谢。
- I understand that inside a
{ } defn, ⍺ is the left argument, and ⍵ is the right argument. What is ⍺⍺ in S←{⍺⌿⍨⍺ ⍺⍺ ⍵}? Similarly, is there an ⍵⍵?
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。如果你像 1 2 3 >S 2 那样调用 S，它的计算结果将是 1 2 3⌿⍨1 2 3 > 2，这将是一个 3.
Does the ⍺ inside the S refer to the left argument of S or the left argument of Q?
在S的正文中，所有由⍺和⍵字符组成的内容都是指S的argument/operand。 Q 的原始参数是不可见的（除非它们首先被分配给一个变量，在这种情况下它们作为变量名是可见的）。
- Why the copious use of commute (
⍨)?
我认为这主要是一种风格选择。我也更喜欢编写带括号的代码而不是在生产代码中使用它，除非这种用法很容易被识别为 APL 习语。我确实写过3÷⍨whatever 而不是 (whatever)÷3 用于除以常数。
- This is not actually performing quicksort, is it?
你是对的。正如您已经提到的，Quicksort 旨在 运行 就地真正成为 Quick (TM)。 APL可以做内存预分配和数组共享来减少一些内存拷贝和分配，但至少在创建三个子数组（元素小于/等于/大于pivot）时，一些拷贝是不可避免的稍后连接。
需要注意的一件事是，与 Haskell 不同，APL 确实具有看起来像 x[i]←v 的就地分配。如果要在 APL 中正确实现快速排序，就必须像在 C 中那样编写代码（将索引传递给递归调用等）。
- Why the use of
≢⍵ to find the dimension size? Why not ⍴⍵?
≢ 称为 "tally" 而 ⍴ 称为 "shape"。 ≢ 总是 returns 一个标量值，而 ⍴ returns 一个向量（如果给定一个向量参数，它将是一个长度为 1 的向量）。虽然标量和长度为一的向量在大多数情况下表现相同，但它们 是 不同的东西，例如1≡,1 是错误的。
我认为区分两者是一个好习惯，只要有可能，就倾向于使用标量而不是长度为一的向量。一个值得注意的例外是当您需要一个显式封闭的数组时（不能封闭标量）。
我正在尝试理解 APL 中的经典快速排序：
Q←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵⌷⍨?≢⍵}
有些东西我不明白，有些文体选择困扰我，所以我要把它们都列出来。我希望有人能给我解释一下。
- 我理解在
{ }定义中，⍺是左参数，⍵是右参数。S←{⍺⌿⍨⍺ ⍺⍺ ⍵}中的⍺⍺是什么？同样，有没有⍵⍵？S里面的⍺是指S的left参数还是Q的left参数？
我的猜测是S里面的⍺指的是S的左参数。 ⍺⍺指的是封闭函数的⍺（即Q的⍺）。
- 为什么大量使用通勤 (
⍨)？代码不是更清楚地写成：
Q←{1≥≢⍵:⍵ ⋄ S←{(⍺ ⍺⍺ ⍵)⌿⍺} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵[?≢⍵]}
我能想到的使用 commute 的唯一用途是减少括号 () 和 [] 的使用，但这似乎不值得牺牲易读性。我在这里遗漏了 "APL way" 的某些内容吗？
这实际上不是在执行快速排序，是吗？快速排序被定义为就地。然而，我对 APL 语义的理解是，这段代码实际上 在递归子调用上构建新数组 ，并使用
⍪连接它们。的确，这就是same criticism that is levelled at Haskell's quicksort。我在 APL 语义中是否遗漏了一些信息来通知此操作已完成 "in-place"？请注意，我对 "sufficiently smart compiler" 参数不感兴趣，因为数组分析从根本上讲具有挑战性。如果 APL 编译器 确实将其转换为就地算法 ，我将非常重视有关它如何设法执行此分析的详细信息 --- 这是一项了不起的成就！为什么要用
≢⍵求维度大小？为什么不⍴⍵？一般来说，我发现人们使用≢而不是⍴来查询最外层维度的大小， 即使函数工作的唯一情况是一维 .同样，我认为我缺少 APL 方式中的某些内容。
非常感谢。
- I understand that inside a
{ }defn,⍺is the left argument, and⍵is the right argument. What is⍺⍺inS←{⍺⌿⍨⍺ ⍺⍺ ⍵}? Similarly, is there an⍵⍵?
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。如果你像 1 2 3 >S 2 那样调用 S，它的计算结果将是 1 2 3⌿⍨1 2 3 > 2，这将是一个 3.
Does the
⍺inside theSrefer to the left argument ofSor the left argument ofQ?
在S的正文中，所有由⍺和⍵字符组成的内容都是指S的argument/operand。 Q 的原始参数是不可见的（除非它们首先被分配给一个变量，在这种情况下它们作为变量名是可见的）。
- Why the copious use of commute (
⍨)?
我认为这主要是一种风格选择。我也更喜欢编写带括号的代码而不是在生产代码中使用它，除非这种用法很容易被识别为 APL 习语。我确实写过3÷⍨whatever 而不是 (whatever)÷3 用于除以常数。
- This is not actually performing quicksort, is it?
你是对的。正如您已经提到的，Quicksort 旨在 运行 就地真正成为 Quick (TM)。 APL可以做内存预分配和数组共享来减少一些内存拷贝和分配，但至少在创建三个子数组（元素小于/等于/大于pivot）时，一些拷贝是不可避免的稍后连接。
需要注意的一件事是，与 Haskell 不同，APL 确实具有看起来像 x[i]←v 的就地分配。如果要在 APL 中正确实现快速排序，就必须像在 C 中那样编写代码（将索引传递给递归调用等）。
- Why the use of
≢⍵to find the dimension size? Why not⍴⍵?
≢ 称为 "tally" 而 ⍴ 称为 "shape"。 ≢ 总是 returns 一个标量值，而 ⍴ returns 一个向量（如果给定一个向量参数，它将是一个长度为 1 的向量）。虽然标量和长度为一的向量在大多数情况下表现相同，但它们 是 不同的东西，例如1≡,1 是错误的。
我认为区分两者是一个好习惯，只要有可能，就倾向于使用标量而不是长度为一的向量。一个值得注意的例外是当您需要一个显式封闭的数组时（不能封闭标量）。