haskell - 使用用户定义的函数在 APL 中减少/扫描如何工作？

Question

我试图在 APL 的 bool 向量中找到最长的不间断 1 链的长度。在 Haskell 中，如果我有一个由 1 和 0 表示的 bool 列表，我可以这样做:

Prelude> scanl (\acc x -> x*(acc+1)) 0 [0,0,1,1,0,1,1,1,1,0,1]
[0,0,0,1,2,0,1,2,3,4,0,1]

然后取最大值。

我尝试在 APL 中做类似的事情:

{⍵×⍺+1}\0 0 1 1 0 1 1 1 1 0 1
0 0 1 2 0 4 8 16 32 0 64

这根本不是我期望的向量。我曾假设 ⍺ 会在扫描/归约的上下文中指代累加器，而 ⍵ 会指代向量的下一个元素，但我的理解似乎有点偏离。这些简单的例子也让我感到困惑:

{⍵}\1 1 1 1 1
1 1 1 1 1
{⍵+⍵}\1 1 1 1 1
1 2 4 8 16
{⍵×⍵}\1 1 1 1 1
1 1 1 1 1

甚至可以(在实践中)在 APL 中使用带有 scan/reduce 的用户定义函数吗？如果是，它是如何工作的，⍺和⍵指的是什么？

Answer 1

首先，让我们看一下基本问题。 ⍺ 和 ⍵ 是匿名函数的左右参数:

      1 {⍺} 2
1
      1 {⍵} 2
2
      1 {⍺+⍵} 2
3

Reduce 和 scan 可以与用户定义的函数一起使用，它们通常是。他们像这样工作¹:

f/1 2 3 4 … ←→ 1 f 2 f 3 f 4 …
f\1 2 3 4 … ←→ (f/1) (f/1 2) (f/1 2 3) (f/1 2 3 4) …

使用这些定义，让我们评估让您感到困惑的示例:

{⍵}\1 1 1 1 1
({⍵}/1) ({⍵}/1 1) ({⍵}/1 1 1) … 
1 (1 {⍵} 1) (1 {⍵} (1 {⍵} 1)) …
1 1 (1 {⍵} 1) …
1 1 1 …

{⍵+⍵}\1 1 1 1 1
({⍵+⍵}/1) ({⍵+⍵}/1 1) ({⍵+⍵}/1 1 1) ({⍵+⍵}/1 1 1 1) …
1 (1 {⍵+⍵} 1) (1 {⍵+⍵} (1 {⍵+⍵} 1)) (1 {⍵+⍵} (1 {⍵+⍵} (1 {⍵+⍵} 1))) …
1 (1+1) (1 {⍵+⍵} (1+1)) (1 {⍵+⍵} (1 {⍵+⍵} (1+1))) …
1 2 (1 {⍵+⍵} 2) (1 {⍵+⍵} (1 {⍵+⍵} 2)) …
1 2 (2+2) (1 {⍵+⍵} 4) …
1 2 4 (4+4) …
1 2 4 8 …

{⍵×⍵}\1 1 1 1 1
…

这里要注意的重要一点是，根据通常的 APL 评估规则，每次减少都是从右到左进行的。将此与 Haskell 的 scanl 进行比较，它返回一个连续减少值的列表，其中每个减少都是从左到右完成的:

scanl f z [x1,x2,…] == [z,z `f` x1,(z `f` x1) `f` x2,…]

因此，使用 scanl 评估第二个示例我们得到:

scanl (\x y -> y+y) 1 [1,1,1,1,1]
[1,(\x y -> y+y) 1 1,(\x y -> y+y) ((\x y -> y+y) 1 1) 1,…]
[1,1+1,(\x y -> y+y) 1+1,…]
[1,2,(\x y -> y+y) 2 1,…]
[1,2,1+1,…]
[1,2,2,…]

Haskell 的 scanr1 ， scanl1 的从右到左对偶, 工作原理类似于 APL 的扫描。 (以 1 结尾的函数的区别仅在于它们不需要起始值):

scanr1 (\x y -> y+y) [1,1,1,1,1]
[…,(\x y -> y+y) 1 ((\x y -> y+y) 1 1),(\x y -> y+y) 1 1,1]
[…,(\x y -> y+y) 1 (1+1),1+1,1]
[…,(\x y -> y+y) 1 2,2,1]
[…,2+2,2,1]
[…,4,2,1]

APL 的扫描实际上介于 scanl 的功能之间和 scanr .虽然减少本身是从右到左完成的，如 scanr ，它返回从左边开始的中间减少，如 scanl :

f\1 2 3 4 ←→ 1 (1 f 2) (1 f (2 f 3)) (1 f (2 f (3 f 4)))

现在，当我们评估您尝试的解决方案时，应该清楚会发生什么:

{⍵×⍺+1}\0 0 1 1 0 1 1 1 1 0 1
({⍵×⍺+1}/0) ({⍵×⍺+1}/0 0) ({⍵×⍺+1}/0 0 1) ({⍵×⍺+1}/0 0 1 1) …
0 (0 {⍵×⍺+1} 0) (0 {⍵×⍺+1} (0 {⍵×⍺+1} 1)) (0 {⍵×⍺+1} (0 {⍵×⍺+1} (1 {⍵×⍺+1} 1))) …
0 (0×1) (0 {⍵×⍺+1} (1×1)) (0 {⍵×⍺+1} (0 {⍵×⍺+1} (1×2))) …
0 0 (0 {⍵×⍺+1} 1) (0 {⍵×⍺+1} (0 {⍵×⍺+1} 2)) …
0 0 (1×1) (0 {⍵×⍺+1} (1×2)) …
0 0 1 (0 {⍵×⍺+1} 2) …
0 0 1 (1×2) …
0 0 1 2 …

关于您实际尝试做的事情，当然有很多解决方案。这是我想出的第一个( v 是零和一的向量):

⌈/¯1+2-⍨/(v=0)/⍳⍴v←0,v,0

由于答案已经很长了，我将分析它作为练习。正如我所说，这只是我想到的第一件事，并且使用了与您不同的方法。我相信一些更有经验的 APLer 会想出更好更优雅的解决方案。

编辑:这是一个尽可能接近你原来方法的解决方案。出于某种原因，我无法让它与 GNU APL 一起工作，这是我通常使用的实现，所以我花了更长的时间。这可能是一个错误，但我不知道。不幸的是，GNU APL 开发人员不太喜欢动态函数等语言扩展，所以它可能是故意的。我一有时间就研究一下。它在 NGN 和 Dyalog 中对我有用。也许它可以进一步改进，但这几乎是您想要做的:

      v ← 0 0 1 1 0 1 1 1 1 0 1
0 0 1 1 0 1 1 1 1 0 1
      {⍺×⍵+1}/¨⌽¨,\v
0 0 1 2 0 1 2 3 4 0 1
      ⌈/{⍺×⍵+1}/¨⌽¨,\v
4

(编辑:正如 Elias 在下面的评论中指出的那样，您可以通过将减少包装在匿名函数中来使其在 GNU APL 中工作: {{⍺×⍵+1}/⍵}¨⌽¨,\v 。)

第二次编辑:这可能是我能想到的最优雅的解决方案:

      v ← 0 0 1 1 0 1 1 1 1 0 1
      ⌈/∊⍴¨⊂⍨v
4

(另外，请注意，上述评估中可能存在一些错误。计算机在这种繁琐的工作中比人类好得多。无论如何，要点应该很清楚。)

¹ 实际上，这过于简单化了。这个解释使用了所谓的插入缩减风格。实现也可能使用封闭式缩减风格，这会导致细微的差异。此外，这是扫描的简单 O(n²) 定义。实现通常会为关联函数使用更有效的实现。