如何使用用户定义的函数在APL中进行缩减/扫描？

Question

我试图在APL的布尔向量中找到最长的1个连续链的长度.在Haskell中,如果我有一个由1和0表示的布尔列表,我可以这样做:

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中使用用户定义的函数和扫描/缩小？如果是这样,它是如何工作的,⍺和what指的是什么？

Answer 1

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

      1 {?} 2
1
      1 {?} 2
2
      1 {?+?} 2
3

减少和扫描可以与用户定义的函数一起使用,它们通常是.他们像这样工作¹:

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²)扫描定义.实现通常会为关联函数使用更有效的实现.}