haskell - 函数式语言如何表示内存中的代数数据类型？

Question

如果您在 Haskell 中编写生物信息学算法，您可能会使用代数数据类型来表示核苷酸:

data Nucleotide = A | T | C | G

我认为，在标准 ML 或 OCaml 中你会做类似的事情(我从来没有真正使用过)。

Nucleotide 类型的值可以清楚地包含在两位中。但是，这样做会导致访问时间比您为每个 Nucleotide 值使用一个字节的情况要慢，因为您需要使用二元运算符选择出感兴趣的两位。

因此，在决定如何表示代数数据类型时，编译器必须在内存效率和计算效率之间做出内在的权衡。此外，由于值可以是可变大小的，因此代数数据类型在内存中的表示变得更加复杂:

data Maybe a = Just a | Nothing

显然，Just a 形式的 Maybe a 值在逻辑上大于 Nothing 形式的值。在这样一个极端的例子中:

data Hulk a b c d e = Big a b c d e | Little

您绝对不想在 Little 值中存储空指针或 Big 值中包含的五个值的零值。我假设您只使用可变大小的堆分配内存，并在开头使用构造函数 ID(例如，0 用于 Big 和 1 代表 Little)。但是，如果您想在堆栈中存储 Hulk 值(一种更快的表示)，则必须将空白内存与 Little 值一起存储，以便所有值Hulk 类型的大小相同。另一个权衡。

Simon Marlow 在 previous StackOverflow question 中回答了我关于 GHC 的一般性问题。 .但是，我有三个相关的问题仍未得到解答:

• 标准 ML(SML/NJ 和 MLton)和 OCaml 使用相同的技术吗？
• 如果是这样，这些语言(或其兄弟语言)的不常见编译器是否会尝试其他技术？
• 在这些语言中是否有一种相当简单的方法(最好是编译指示或选项标志)来使用内存效率更高的表示，例如 Nucleotide 的两位表示？这种内存效率对于许多生物信息学应用来说是必要的；如果每个 Nucleotide 必须是一个字节，那么高性能的生物信息学算法将不得不求助于手动位摆弄。

Answer 1

没有单一的答案:数据类型是抽象结构，可以根据实现者的判断以多种方式实现。在实践中，诸如单独编译之类的考虑往往会有所限制。

对于将仅包含空构造函数的数据类型打包到尽可能少的位的特定情况，您可以继续定义从数据类型到小整数并返回的函数。被抽象类型(或者在 Haskell 中，newtype)隐藏的整数类型也是一个合理的选择。将小整数打包和解包为您正在使用的任何聚合形式将是您的工作。

顺便说一句，Real World OCaml 有 a very nice chapter关于 OCaml 值的表示(粗略总结:就本问题而言，与 GHC 没有太大不同)。