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

Question

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

根据 Real World Ocaml ，没有参数的多态变体仅存储为未装箱的整数。为方便起见，这里转载了摘录。

A polymorphic variant without any parameters is stored as an unboxed integer and so only takes up one word of memory, just like a normal variant. This integer value is determined by applying a hash function to the name of the variant. The hash function isn't exposed directly by the compiler, but the type_conv library from Core provides an alternative implementation: ...

然而，多态比较似乎并不对整数值进行操作，并且似乎尊重多态变体名称的字典顺序(至少在顶级)。

# 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 的短字符串，这将倾向于保留词汇顺序。