list - F#中是否有像Array2D一样的List2D

Question

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

Answer 1

简短回答:不，没有二维列表。

更长的答案:

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

F# 列表和数组根本不是一回事。让我们回顾一下人们认为二维版本具有的有关 F# 列表的一些事实。他们:

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

二维 F# 列表的等价物可以被认为是类似格子结构的矩形，如下所示:

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

其中-表示左边的节点持有对右边的引用，|表示上面的节点持有对下面节点的引用。就像在一维列表中一样，每个节点都将包含一个完整的二维列表，即矩形中从其自身到右下角最后一个节点的所有元素。

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

• 新元素在节点的最下面一行
• 新元素在最右边的一列节点中
• 从新节点向下或向右移动一级形成的元素(以及二维列表)是非空的并且能够组合成一致的二维列表。

这就是麻烦所在。在结构比较的世界中，您如何判断这两个邻居建立在相同的子列表上？您可以通过右下和右下路径从新节点沿着对角线向下移动一步，看看您是否最终到达同一元素。如果结果不同(由于参数无效而失败)或引用相同(新的二维列表有效)，这很好而且花花公子，但是如果它们的内容相等但它们的身份不相等怎么办？换句话说:它们是不同的对象但可能是等价的？现在，我们被迫遍历整个事物并比较所有事物，否则我们最终可能会构建一些根本不是二维的疯狂图表。

这需要比较整个子列表，这将是从新插入节点到最右下节点的节点一步对角线的矩形。那不太实际；像这样构建一个包含 n 个元素的二维列表的复杂度为 O(n^2) - 除非有某种形式的优化，例如跟踪所有节点并为等效节点提供唯一标识。

此时，我想我明白了为什么像这样的东西没有进入 F# 核心库。