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

Question

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

data Nucleotide = A | T | C | G

你会在标准ML或OCaml中做同样的事情,我假设(我从来没有真正使用过).

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

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

data Maybe a = Just a | Nothing

显然,Maybe a表单的值在Just a逻辑上大于表单的值Nothing.在这样一个极端的例子中:

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

你肯定不希望存储Little值null指针或值中包含的五个值的零Big值.我假设你只是使用堆分配的可变大小的内存,在开头有一个构造函数ID(例如,0for Big和1for Little).但是,如果要Hulk在堆栈上存储值(表示更快),则必须将空白内存与Little值一起存储,以使该类型的所有值Hulk都具有相同的大小.另一个权衡.

Simon Marlow在之前的StackOverflow问题中回答了关于GHC的一般问题.但是,我有三个相关的问题仍然没有答案:

• 标准ML(SML/NJ和MLton)和OCaml使用相同的技术吗？
• 如果是这样,这些语言(或他们的兄弟姐妹)的任何不太常见的编译器是否会尝试其他技术？
• 在这些语言中是否有一种相当简单的方法(理想情况下是一个pragma或选项标志)来使用更高效的内存表示,比如两位表示Nucleotide？这种记忆效率对于许多生物信息学应用是必要的; 如果每个Nucleotide必须是一个字节,高性能生物信息学算法将不得不诉诸手动比特摆弄.

Answer 1

没有单一的答案：数据类型是抽象结构，可以由实现者自行决定以多种方式实现。在实践中，诸如单独编译之类的考虑往往会在某种程度上限制事物。

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

顺便说一句，Real World OCaml 有一个关于 OCaml 值表示的非常好的章节（粗略总结：就这个问题而言，与 GHC 没有太大不同）。