10

我会直截了当地说 - 有没有办法在 Haskell 中拥有一个动态大小的恒定时间访问数据结构，就像任何其他命令式语言中的数组一样？

我确信某处有一个模块可以为我们神奇地做到这一点，但我希望能对人们如何以一种功能性的方式做到这一点有一个一般性的解释:)

据我所知，Map使用二叉树表示，因此它具有O(log(n))访问时间，并且列表当然具有O(n)访问时间。

此外，如果我们让它不可变，它就会是纯的，对吧？

有什么想法可以解决这个问题（除了Array = Array { one :: Int, two :: Int, three :: Int ...}模板 Haskell 等）吗？

4

4 回答 4

8

如果您的键是同构的，Int那么您可以使用IntMapO(min(n,W))，因为它的大多数操作n是单个操作收敛到一个常数。WInt

于 2013-11-07T09:42:12.003 回答
5

Haskell 中动态大小的常量时间访问数据结构，

  • 数据数组
  • 数据.向量

等等等等

对于关联结构，您可以选择：

  • Log-N 树和树结构
  • 哈希表
  • 混合哈希映射尝试

具有各种不同的对数复杂度和常数因子。

所有这些都在hackage上。

于 2013-11-07T11:15:43.457 回答
2

除了其他好的答案之外，这样说可能会很有用：

当仅限于代数数据类型和纯度时，所有动态大小的数据结构必须至少具有对数最坏情况访问时间。

就我个人而言，我喜欢称其为纯洁的代价。

Haskell 为您提供了三种主要的解决方法：

  • 改变问题：使用散列或前缀树。
  • 对于恒定时间读取，请使用纯数组或更新的Vectors；它们不是 ADT，需要编译器支持/内部隐藏 IO。恒定时间写入是不可能的，因为纯度禁止修改原始数据结构。
  • 对于恒定时间写入，请使用IOor STmonad，ST尽量避免外部可见的副作用。这些 monad 在编译器中实现。
于 2014-03-01T03:05:51.453 回答
1

确实，如果没有编译器/运行时魔法，您就无法在 Haskell 中拥有恒定时间访问数组。

然而，这不是（仅仅）因为 Haskell 是函数式的。Java 和 C# 中的数组也需要运行时魔法。在 Rust 中，您可能能够在不安全的代码中实现它们，但不能在安全的 Rust 中实现。

事实上，任何不允许你分配动态大小的内存，或者不允许你使用指针的语言都需要运行时魔法来实现数组。

这不包括任何安全语言，无论是面向对象的还是函数式的。

Haskell 和例如之间的唯一区别。Java 相对于数组，是数组在 Haskell 中的用处远不如在 Java 中有用，但在 Java 中，数组对于我们所做的一切都是如此核心，以至于我们甚至没有注意到它们是魔法。

尽管有一种方法，Haskell 需要比例如更多的数组魔法。爪哇。

使用 Java，您可以初始化一个空数组（这需要魔法），然后用值填充它（不需要）。

使用 Haskell，这显然会违背不变性。所以任何数组都必须用它的值初始化。因此，编译器的魔力不仅仅延伸到给你一个空的内存块来索引。它还需要为您提供一种使用值初始化数组的方法。因此，数组的创建和初始化必须是一个步骤，完全由编译器处理。

于 2018-11-28T18:56:14.453 回答