代码之家 › 专栏 › 技术社区 › ackien

如何使用用户定义的功能减少/扫描APL?

apl functional-programming haskell

ackien · 技术社区 · 10 年前

我试图在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中,甚至有可能(在实践中)使用具有扫描/减少功能的用户定义功能吗?如果是,它是如何工作的,以及它的作用和指的是什么?

2 回复 | 直到 10 年前

danlei 10 年前

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

      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 (\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的扫描功能实际上介于 扫描 和 scanr 。而缩减本身是从右向左进行的,如 扫描仪 ,它返回从左边喜欢 扫描 :

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 是0和1的向量):

â/Â¯1+2-â¨/(v=0)/â³â´vâ0,v,0

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

编辑:这是一个尽可能接近您最初方法的解决方案。由于某种原因,我无法让它与GNUAPL一起工作,这是我通常使用的实现,所以我花了一些时间。这可能是一个bug,但我不知道。不幸的是,GNUAPL开发人员不太喜欢像动态函数这样的语言扩展,所以这可能是故意的。我有时间时会调查的。我在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在下面的评论中指出的那样,你可以通过在一个匿名函数中包装缩减来在GNUAPL中实现这一点: {{âºÃâµ+1}/âµ}Â¨â½Â¨,\v .)

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

      v â 0 0 1 1 0 1 1 1 1 0 1
      â/ââ´Â¨ââ¨v
4

(此外,请注意,上述评估中可能存在一些错误。计算机比人类更擅长这种乏味的工作。无论如何,要点应该很清楚。)

^{事实上,这是一个过于简单的说法。这个解释使用了所谓的

插入缩减样式。

实现还可以使用

封闭缩减样式,

这导致细微的差异。此外,这是扫描的原始O(n)定义。实现通常会对关联函数使用更有效的实现。}

Lobachevsky 10 年前

对于一个老派APLer来说,这个问题看起来很像 分区正归约 在嵌套阵列出现和出现之前,分区技术一直被大量使用,直到20世纪80年代末。有关详细信息,请参阅

www.sudleyplace.com/APL/boolean.pdf(第10页为pPLRED,第15页为其助手函数N-delta)

和

http://www.chilton.com/~jimw/apl85.html (搜索pPLUSRED)