OCaml如何通过文本表示对多态变体进行排序？

Question

在OCaml中，通过遍历由immediates和指向块的指针组成的值的运行时表示来实现多态比较。

根据Real World Ocaml，没有参数的多态变体只是存储为未装箱的整数。为方便起见，此处摘录。

没有任何参数的多态变体存储为未装箱的整数，因此只占用一个内存字，就像普通变量一样。通过将哈希函数应用于变体的名称来确定此整数值。散列函数不是由编译器直接公开的，但是来自Core的type_conv库提供了另一种实现：...

然而，多态比较似乎不对整数的值进行操作，并且似乎遵守多态变体名称的词典排序（至少在顶层）。

# List.sort Pervasives.compare
     [ `L ; `K ; `J ; `I ; `H ; `G ; `F ; `E ; `D; `C ; `B; `A ];; 
[`A; `B; `C; `D; `E; `F; `G; `H; `I; `J; `K; `L]

有一个小皱纹：表示的长度似乎在排序中最重要。

# List.sort compare  [ `BBBB; `AAAA; `AAA; `ABA; `BB; `ZZ; `AA ];; 
[`AA; `BB; `ZZ; `AAA; `ABA; `AAAA; `BBBB]

OCaml如何解决这个问题？ OCaml如何在运行时按字典顺序对变体进行排序？不应该没有任何参数的多态变体与普通整数无法区分吗？

OCaml实现者是否选择了哈希函数，通过巧合/设计，对于短变体名称具有此行为？

Answer 1

由于其构造，哈希函数保留了短字符串的顺序。但这不是一般财产。

# List.sort compare [`AAAAAAA; `BAAAAAA; `CAAAAAA];;
- : [> `AAAAAAA | `BAAAAAA | `CAAAAAA ] list =
       [`BAAAAAA; `CAAAAAA; `AAAAAAA]
#

对于OCaml 4.06.0，散列代码如下所示：

CAMLexport value caml_hash_variant(char const * tag)
{
  value accu;
  for (accu = Val_int(0); *tag != 0; tag++)
    accu = Val_int(223 * Int_val(accu) + *((unsigned char *) tag));
#ifdef ARCH_SIXTYFOUR
  accu = accu & Val_long(0x7FFFFFFFL);
#endif
  /* Force sign extension of bit 31 for compatibility between 32 and 64-bit
     platforms */
  return (int32_t) accu;
}

在我看来，对于代码小于223的短字符串，这将倾向于保留词汇顺序。