类型可存储的确切标准是什么？

Question

很久以前我实现了对称群（和循环群）的数据类型：

newtype Cyclic (n :: Nat) = Cyclic {cIndex :: Integer}

data Symmetric (n :: Nat) where
    S1 :: Symmetric 1
    (:.) :: Cyclic n -> Symmetric (n-1) -> Symmetric n

这是一个不均匀的容器，~~但我不确定这是数组还是列表。~~正如评论所阐明的那样，这不是问题。

~~如果这是一个数组，~~就可以实现instance Storable (Symmetric n)。为什么可以这样做？

Answer 1

Storable 旨在唤起 C struct 的想法。作为 struct，任何 Storable 的类型都有大小限制。 Storable (Symmetric n) 是可能的，因为 Symmetric n 事实上是有界的。（假设 Cyclic ns 等价于模 n，）它有 n! 个值，这是有限的，所以你不需要无界的 space。更具体地说，仅 log2(n!) 位就足够了。请注意，我说的是 Symmetric n 某些特定的 n。对于不同的Nat，n、m等。Symmetric n、Symmetric m等是不同的类型，因此它们可能具有不同的大小。对于单个 n :: Nat，Symmetric n具有固定大小。

真正的问题是选择编码。为了便于实施，您可以使用递归编码，其中 Storable n 由 ceil(log2(n) / 8) 字节组成，用于保存第一个数字，后跟 Storable (n - 1)。然后，Symmetric 1 将是 0 个字节，Symmetric 2 将是 1 个字节（仅使用其中一位），Symmetric 3 将是 2 个字节，...，Symmetric 256将是 255 个字节，Symmetric 257 将是 257 个字节（因为第一个数字有 257 个选择，因此需要两个字节）。这当然效率不高，但您可以清楚地看到每个 Symmetric n 都有一个明确定义的大小。如果你想达到 log2(n!) 位的界限（实际上，ceil(log2(n!)/8) 字节），你必须做一些 ~~funky 数学~~（我不熟悉），但你可以做到。

你需要单例才能完成这项工作；可以这样写

instance KnownNat n => Storable (Symmetric n)

但不是

instance Storable (Symmetric n)

类型被擦除，所以第二个 instance 没有被告知 n 是什么，因此无法读取任何内容（或实现 sizeof，等等）。它可以写入，因为 Symmetric 是一个 GADT，因此包含有关 n 是什么的信息。

旁注：Symmetric 0 不应该是非空的吗？

data Symmetric (n :: Nat) where
    S0 :: Symmetric 0
    (:.) :: Cyclic n -> Symmetric (n - 1) -> Symmetric n

Symmetric 0 是从空集到自身的双射集合，并且该集合中只有一个函数（空集）。

类型可存储的确切标准是什么？

What is the exact criteria for a type to be Storable?

haskell

containers

gadt

data-kinds