functional-programming - 我应该在 OCaml 的 List 上实现 PriorityQueue (Heap) 吗？

Question

我知道 priorityQueue 在 Array 上是完美的，因为它的性质就位。

我应该在 OCaml 中的 List 上实现 PriorityQueue(堆)吗？

如果我在 List 上这样做，那么我必须删除 in-place 东西并想办法每次创建一个每一步都有新列表。所以我想知道这是否值得。

---

其实我对此有更深层次的思考。

因此，许多基础算法/数据结构都是从in-place发明的(我使用invented因为我知道很多in-place可以是转换为 not-in-place)。

但是，FL 不推荐mutable 的东西。我的另一个问题是如何在in-place/mutable 和immutable 之间做出选择？ 或者在OCaml 中，我什么时候应该选择在 list 和 array 之间选择？

---

例如，在上面的priorityqueue案例中，如果我被要求用OCaml写一个priorityqueue，我应该更喜欢array吗？是更自然更容易，还是为了不可变我应​​该选择列表？

Answer 1

使用不可变数据在模块化和可靠性方面带来了惊人的好处。从本质上讲，数据不可能通过其他模块的修改而损坏。模块不再需要担心其他模块，以及谁“拥有”数据。在您不再需要这样做之前，您不会意识到这是多么繁重。另一个意想不到的好处是，它变得更容易推断代码的行为，因为它的行为就像一个数学函数。我在实践中经历过这两种情况，这让我成为了 FP 的信徒。成本通常出奇地适中，要么是一个很小的常数因子，要么可能是一个额外的 log n。

不可变数据的另一个优势是持久性，即无需额外努力即可维护数据历史状态的能力。 (在不可变环境中实现撤消操作很有趣。)

也就是说，我有时会使用可变数据，因为它可以更快。

作为元评论，我建议您花一些时间在 OCaml 中仅使用不可变数据。如果没有别的，它最初会成为一个非常有趣的谜题。在获得一些直接经验之后，您将能够判断在特定情况下的权衡所在。所以我建议您尝试实现一个不可变的优先级队列(或阅读其他人是如何做到的)。