APL 中的惯用图表
Idiomatic graphs in APL
APL 非常适合解决数组类型问题，但我很好奇如何在 APL 中最好地处理图形。我正在研究 leet 问题，例如问题 662. Maximum Width of Binary Tree，该练习使用具有 value/left/right 指针样式的 Node 对象，但是测试用例使用像 [1,3,null,5,3] 这样的基本数组。符号被压缩；未压缩将是 [[1], [3,null], [5,3,null,null]]。逐层阅读给出[[1], [3], [5,3]]（所以2是最宽的层）。
另一个例子,
[5,4,7,3,null,2,null,-1,null,9]给出答案2
所以我不确定处理树木的惯用方式。我使用 类 吗？还是数组最好？无论哪种情况，如何转换输入？
我想出了几个解决方案，但都感觉不够优雅。 （评论不足请见谅）
convert←{
prev ← {(-⌈2÷⍨≢⍵)↑⍵}
nxt←{
⍵≡⍬:⍺
m←2/×prev ⍺
cnt←+/m
(⍺,(m\cnt↑⍵))nxt(cnt↓⍵)
}
(1↑⍵)nxt(1↓⍵)
}
或者，
convert ← {
total←(+/×⍵)
nxt←{
double←×1,2↓2/0,⍵
(((+/double)↑⍺)@⊢)double
}
⍵ nxt⍣{(+/×⍺)=total}1
}
这两种解决方案都有局限性，因为它们假设 0 是 null。
一旦我解压缩了输入，这只是按顺序分层的问题
⌈/(1+⌈/-⌊/)∘⍸¨×nodes⊆⍨⍸2*¯1+⍳⌈2⍟≢nodes
在 Python 中，尽管我可以使用其他方法进行遍历，即在每个深度的基础上跟踪 left/right-most 节点。
注意：这可能是两个问题，一个是解压，一个是一般如何遍历图，但是一个要看另一个
有什么想法吗？
Co-dfns 编译器的工作提供了很多关于像使用 APL 的数据结构一样工作 tree/graph 的见解。
论文：A Data Parallel Compiler Hosted on the GPU
GitHub repo: github.com/Co-dfns/Co-dfns（项目自述文件中的许多相关内容）
但是这篇论文很长，所以对于这个特定的练习，我会简要解释一下如何处理它。
the exercise works with Node objects with a value/left/right pointer style, however the test-case uses a basic array like [1,3,null,5,3].
我们真的用 Node 类型的对象构建树来获得问题的答案吗？您可以用 Python 之类的方式编写解决方案并转换为 APL，但这将失去用 APL 编写它的全部意义...
注意输入已经是一个数组！它是二叉树的 bfs 遍历。 （不过 co-dfns 编译器使用 dfs 遍历顺序）
所以，实际上我们需要做的只是为像 [1,3,2,5,3,null,9] 这样的输入构建一个如下所示的矩阵（⍬ 是 null 的占位符值）：
1 ⍬ ⍬ ⍬ ⍝ level 0
3 2 ⍬ ⍬ ⍝ level 1
5 3 ⍬ 9 ⍝ level 2
对于这个问题我们不需要知道哪个节点的父节点是哪个。
我们甚至可以做一些类似的事情，通过滥用输入没有负值的事实（即使数字可能是负数，实际上我们只关心它是否为空），并将 ⍬ 更改为 ¯1 或0 并且更容易计算答案。
所以问题变成了：“从输入数组计算树的矩阵表示作为变量tree，然后通过+/0<tree计算每个级别的宽度，那么输出只是 2*level（注意第一级是 0 级）” 这是对宽度使用了错误的定义。我将在下面展示如何更正它
而且输入到矩阵的转换其实很简单，提示：↑.
1 (3 2) 5
┌─┬───┬─┐
│1│3 2│5│
└─┴───┴─┘
↑1 (3 2) 5
1 0
3 2
5 0
感谢指出我原来的方案在构建树矩阵时有问题
这是构建树的更正方法。为了区分空值和填充的 0，我在输入数组中添加了一个，因此 2 用于 non-null，1 用于空值。
buildmatrix←{
⎕IO←0
in←1+(⊂⊂'null')(≢⍤1 0)⎕JSON ⍵
⍝ Build the matrix
loop←{
(n acc)←⍺
0=≢⍵:acc
cur←n↑⍵
(2×+/2=cur)(acc,⊂cur)∇ n↓⍵
}
↑1 ⍬ loop in
}
然而，由于此处宽度的定义是：
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.
我们可以在尝试重建树时只计算宽度（使用 \ 和 / 以及上一级的模式计算每个级别的宽度）：
如果上一级是1011，下一级是100010
1 0 1 1
1 0 0 0 0 0 1 0
(2/1 0 1 1) 0 0 0 1 0
1 0 0 0 0 0 1 0
所以不需要构建完整的矩阵，练习的答案就是：
width←{
⎕IO←0
in←(⊂⊂'null')(≢⍤1 0)⎕JSON ⍵
⍝ strip leading trailing zero
strip←(⌽⍳∘1↓⊢)⍣2
⍝ Build the matrix
loop←{
(prev mw)←⍺
0=≢⍵:mw
cur←⍵↑⍨n←2×+/prev
((⊢,⍥⊂mw⌈≢)strip cur\⍨2/prev)∇ n↓⍵
}
(,1)1 loop 1↓in
}
width '[1,null,2,3,null,4,5,6]'
2
有趣的是，您可以在其他基于 non-array 的语言（例如 Haskell 中执行相同的操作。因此，与其在外观相似的语言之间转换现有算法，不如以 APL 的方式思考，找到解决问题的新算法！
APL 非常适合解决数组类型问题，但我很好奇如何在 APL 中最好地处理图形。我正在研究 leet 问题，例如问题 662. Maximum Width of Binary Tree，该练习使用具有 value/left/right 指针样式的 Node 对象，但是测试用例使用像 [1,3,null,5,3] 这样的基本数组。符号被压缩；未压缩将是 [[1], [3,null], [5,3,null,null]]。逐层阅读给出[[1], [3], [5,3]]（所以2是最宽的层）。
另一个例子,
[5,4,7,3,null,2,null,-1,null,9]给出答案2
所以我不确定处理树木的惯用方式。我使用 类 吗？还是数组最好？无论哪种情况，如何转换输入？
我想出了几个解决方案，但都感觉不够优雅。 （评论不足请见谅）
convert←{
prev ← {(-⌈2÷⍨≢⍵)↑⍵}
nxt←{
⍵≡⍬:⍺
m←2/×prev ⍺
cnt←+/m
(⍺,(m\cnt↑⍵))nxt(cnt↓⍵)
}
(1↑⍵)nxt(1↓⍵)
}
或者，
convert ← {
total←(+/×⍵)
nxt←{
double←×1,2↓2/0,⍵
(((+/double)↑⍺)@⊢)double
}
⍵ nxt⍣{(+/×⍺)=total}1
}
这两种解决方案都有局限性，因为它们假设 0 是 null。
一旦我解压缩了输入，这只是按顺序分层的问题
⌈/(1+⌈/-⌊/)∘⍸¨×nodes⊆⍨⍸2*¯1+⍳⌈2⍟≢nodes
在 Python 中，尽管我可以使用其他方法进行遍历，即在每个深度的基础上跟踪 left/right-most 节点。
注意：这可能是两个问题，一个是解压，一个是一般如何遍历图，但是一个要看另一个
有什么想法吗？
Co-dfns 编译器的工作提供了很多关于像使用 APL 的数据结构一样工作 tree/graph 的见解。
论文：A Data Parallel Compiler Hosted on the GPU
GitHub repo: github.com/Co-dfns/Co-dfns（项目自述文件中的许多相关内容）
但是这篇论文很长，所以对于这个特定的练习，我会简要解释一下如何处理它。
the exercise works with Node objects with a value/left/right pointer style, however the test-case uses a basic array like
[1,3,null,5,3].
我们真的用 Node 类型的对象构建树来获得问题的答案吗？您可以用 Python 之类的方式编写解决方案并转换为 APL，但这将失去用 APL 编写它的全部意义...
注意输入已经是一个数组！它是二叉树的 bfs 遍历。 （不过 co-dfns 编译器使用 dfs 遍历顺序）
所以，实际上我们需要做的只是为像 [1,3,2,5,3,null,9] 这样的输入构建一个如下所示的矩阵（⍬ 是 null 的占位符值）：
1 ⍬ ⍬ ⍬ ⍝ level 0
3 2 ⍬ ⍬ ⍝ level 1
5 3 ⍬ 9 ⍝ level 2
对于这个问题我们不需要知道哪个节点的父节点是哪个。
我们甚至可以做一些类似的事情，通过滥用输入没有负值的事实（即使数字可能是负数，实际上我们只关心它是否为空），并将 ⍬ 更改为 ¯1 或0 并且更容易计算答案。
所以问题变成了：“从输入数组计算树的矩阵表示作为变量tree，然后通过+/0<tree计算每个级别的宽度，那么输出只是 （注意第一级是 0 级）” 这是对宽度使用了错误的定义。我将在下面展示如何更正它2*level
而且输入到矩阵的转换其实很简单，提示：↑.
1 (3 2) 5
┌─┬───┬─┐
│1│3 2│5│
└─┴───┴─┘
↑1 (3 2) 5
1 0
3 2
5 0
感谢指出我原来的方案在构建树矩阵时有问题
这是构建树的更正方法。为了区分空值和填充的 0，我在输入数组中添加了一个，因此 2 用于 non-null，1 用于空值。
buildmatrix←{
⎕IO←0
in←1+(⊂⊂'null')(≢⍤1 0)⎕JSON ⍵
⍝ Build the matrix
loop←{
(n acc)←⍺
0=≢⍵:acc
cur←n↑⍵
(2×+/2=cur)(acc,⊂cur)∇ n↓⍵
}
↑1 ⍬ loop in
}
然而，由于此处宽度的定义是：
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.
我们可以在尝试重建树时只计算宽度（使用 \ 和 / 以及上一级的模式计算每个级别的宽度）：
如果上一级是1011，下一级是100010
1 0 1 1
1 0 0 0 0 0 1 0
(2/1 0 1 1) 0 0 0 1 0
1 0 0 0 0 0 1 0
所以不需要构建完整的矩阵，练习的答案就是：
width←{
⎕IO←0
in←(⊂⊂'null')(≢⍤1 0)⎕JSON ⍵
⍝ strip leading trailing zero
strip←(⌽⍳∘1↓⊢)⍣2
⍝ Build the matrix
loop←{
(prev mw)←⍺
0=≢⍵:mw
cur←⍵↑⍨n←2×+/prev
((⊢,⍥⊂mw⌈≢)strip cur\⍨2/prev)∇ n↓⍵
}
(,1)1 loop 1↓in
}
width '[1,null,2,3,null,4,5,6]'
2
有趣的是，您可以在其他基于 non-array 的语言（例如 Haskell 中执行相同的操作。因此，与其在外观相似的语言之间转换现有算法，不如以 APL 的方式思考，找到解决问题的新算法！