Как функциональные языки представляют алгебраические типы данных в памяти?

Если бы вы писали алгоритм биоинформатики на Haskell, вы, вероятно, использовали бы алгебраический тип данных для представления нуклеотидов:

data Nucleotide = A | T | C | G

Я полагаю, вы поступили бы так же в Standard 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 значения нулевые указатели или нулевые значения для пяти значений, содержащихся в Big значениях. Я предполагаю, что вы просто использовали бы память переменного размера, выделенную кучей, с идентификатором конструктора в начале (например, 0 для Big и 1 для Little). Однако, если вы хотите сохранить Hulk значений в стеке (более быстрое представление), вам нужно будет сохранить пустую память вместе со значениями Little, чтобы все значения типа Hulk имели одинаковый размер. Еще один компромисс.

Саймон Марлоу ответил на мой общий вопрос относительно GHC в предыдущем вопросе StackOverflow. Однако у меня есть три связанных вопроса, на которые нет ответа:

• Используют ли стандартный ML (SML / NJ и MLton) и OCaml один и тот же метод?
• Если да, то экспериментируют ли какие-либо менее распространенные компиляторы этих языков (или их братьев и сестер) с другими методами?
• Есть ли в этих языках достаточно простой способ (в идеале - прагма или флаг опции) использовать более эффективное представление памяти, например двухбитное представление Nucleotide? Такая эффективность памяти необходима для многих приложений биоинформатики; если бы каждый Nucleotide должен был быть одним байтом, высокопроизводительные алгоритмы биоинформатики должны были бы прибегнуть к ручной настройке битов.