在F#中是否有类似Array2D的List2D

Question

我是否必须在所有2D操作中使用Array2D然后将它们转换为List2D？任何方便的函数调用或库来定义和操作2D列表？

Answer 1

简答:不,没有二维清单.

更长的回答:

我认为这样的类型在创建时会有问题,因为它的直接实现要么在其等效的cons操作上不具有O(1)复杂性,要​​么破坏结构相等性.

F#列表和数组完全没有相同之处.让我们回想起一些关于F#列表的事实,人们会认为它们具有2d版本.他们:

• 是不可改变的
• 支持结构比较
• 可以通过前置元素迭代构建

两个维度中的F#列表的等价物可以被认为是格子状结构中的矩形,例如:

    N: Node           N-N-0
    0: None           | |
                    N-N-N-0
                    | | |
                N-N-N-N-N-0
                | | | | |
                0 0 0 0 0

其中-表示左侧节点保持对右侧的引用,并|表示上述节点保存对下面节点的引用.就像在一维列表中一样,每个节点将包括完整的2d列表,即矩形中从其自身到右下角的最后一个节点的所有元素.

由于列表应该是不可变的但允许从子列表进行迭代构造,因此通过添加节点创建新列表仅在以下三种情况下有效:

• 新元素位于最下面的一行节点中
• 新元素位于最右边的节点列中
• 通过从新节点向下或向右一步形成的元素(以及因此的2d列表)是非空的并且能够组合成一致的2d列表.

这就是麻烦的来源.你怎么知道这两个邻居在结构比较的世界中建立在相同的子列表上？您可以通过右下和右下路径从新节点沿对角线向下一步,看看您是否最终处于同一元素.如果结果不同(由于参数无效而失败)或引用相同(新的2d列表有效),这是好的和花花公子,但是如果它们的内容相同但是它们的身份不同呢？换句话说:它们是不同的对象但可能是等价的？现在,我们被迫完成整个事情并比较一切,否则我们最终可能会构建一些非二维的疯狂图形.

这需要比较整个子列表,这些子列表是从新插入的节点到最右下的节点一步对角的节点的矩形.那不太实际; 构建像这样的n个元素的2d列表将具有O(n ^ 2) - 除非存在某种形式的优化,例如跟踪所有节点并给予等效节点唯一标识.

在这一点上,我想我可以看到为什么这样的东西没有进入F#核心库.