在SML中实现更快的Fifo

Question

是否有一个Fifo的实现，支持其功能的一个子集，即Enqueue，Dequeue，isEmpty，以及使用某种可变指针的一般empty对象的初始化'a，这样就不会产生复制一个列出当前两个列表实现使用的特定时间（当复杂性被分摊时没有，因为它仍然是O（1）摊销的运营成本，但仍然不适合我的一个应用程序）如果是，那究竟是什么？

Answer 1

您可以使用Array作为dynamic array solution，这也会产生摊销成本，或者您可以使用doubly-linked lists和ref类型实现option。我已经链接到C解决方案，因为这些解决方案是类似的，虽然在SML中语法更复杂，并且因为我在SML中找不到任何示例。双链表解决方案将在每个节点装箱时产生内存开销，但不会产生动态阵列解决方案或您描述的全功能双端队列的摊销成本。

功能性双端队列一直是许多研究的主题;在this Wikipedia article中有一些关于几种数据结构和方法的参考文献都依赖于懒惰而不是懒惰。我不知道他们中的任何一个都是O（1）;似乎他们都是O（1）摊销或O（lg n），但仍然有效。

以下是非功能性双向链表数据类型的外观：

datatype 'a node = Node of { elem : 'a
                           , prev : 'a node option ref
                           , next : 'a node option ref
                           }

datatype 'a deque = Empty | NonEmpty of 'a node

这种实现有一些缺点：

• 跟踪引用在语法上并不好。在C你可以写 if (nd->prev) nd->prev->next = nd; 但是在SML中看起来更加模糊，除非你定义了一堆辅助函数来获取和设置上一个/下一个节点。即使你这样做，由于引用不常用，你的getter和setter看起来会像C的指针语法一样非标准。
• 你正在重新发明空指针。实现本身很脆弱，因为你可能会遇到上一个/下一个节点是NONE的引用的情况。操作不会超越推，弹，移位和不移位，所以当你制作这些操作时，你可以依靠测试（单元或基于属性）。我绝对不得不测试这个，而不是购买通常由ML使用的优势。
• 你的队列是可变的，所以现在你必须小心你传递它的位置。如果您对队列的使用进入破坏状态，则无法轻易找到导致它的源。你基本上用更粗糙的语法编写C语言。

所以简短的回答是：你绝对可以编写相同的实现，但语言并不鼓励这样做，而且函数式程序员通常依赖于具有对数或摊销运行时间的不可变数据结构。