函数式语言如何在内存中表示代数数据类型？
如果您在Haskell中编写生物信息学算法，您可能会使用代数数据类型来表示核苷酸：
data Nucleotide = A | T | C | G
你会在Standard ML或OCaml中做类似的事情，我假设（我从来没有真正使用过）。
Nucleotide类型的值可以清楚地包含在两位中。 但是，这样做会导致访问时间比使用每个Nucleotide值一个字节的速度慢，因为您需要使用二元运算符选择两个感兴趣的位。
因此，在决定如何表示代数数据类型时，编译器必须在内存效率和计算效率之间进行内在的折衷。 此外，由于值的大小可变，因此内存中的代数数据类型的表示会变得更加复杂：
data Maybe a = Just a | Nothing
显然， Just a的形式的Maybe a值也Maybe a比Nothing形式的值大。 在这样一个极端的例子中：
data Hulk a b c d e = Big a b c d e | Little
您肯定不希望为Big值中包含的五个值存储Little值空指针或零值。 我假设你只是使用可变大小的堆分配内存，并在开始时使用构造函数ID（例如， 0代表Big ， 1代表Little ）。 但是，如果您想将Hulk值存储在堆栈上（快速表示），则必须将空白内存与Little值一起存储，以便Hulk类型的所有值都是相同的大小。 另一个折衷。
Simon Marlow在之前的StackOverflow问题中回答了关于GHC的一般问题。 但是，我有三个相关问题尚未解答：
Nucleotide的两位表示？ 这种记忆效率对于许多生物信息学应用是必需的; 如果每个Nucleotide必须是一个字节，高性能生物信息学算法将不得不求助于手动位摆动。 没有单一的答案：数据类型是抽象的结构，可以在执行者的判断下以各种方式实现。 在实践中，诸如单独编译的考虑往往会在某种程度上限制事物。
对于将仅包含零位构造函数的数据类型打包为尽可能少的数据类型的特定情况，您可以继续将函数从数据类型定义为小整数和后退。 一个抽象类型隐藏的整型（或者Haskell， newtype ）也是一个合理的选择。 将小整数打包并解包成任何你正在使用的总体形式将是你的工作。
顺便说一下，真实世界OCaml在OCaml值的表示方面有一个非常好的章节（粗略总结：对于这个问题，与GHC没有太大的区别）。
链接地址: http://www.djcxy.com/p/80199.html上一篇: How do functional languages represent algebraic data types in memory?