F# 和 Haskell 中向量维度的类型约束（依赖类型）

Question

我是 F# 和 Haskell 的新手，正在实施一个项目以确定我更愿意将更多时间投入到哪种语言中。

在很多情况下，我希望给定的数值类型具有基于给定顶级函数的参数（即在运行时）的给定维度。例如，在这个 F# 片段中，我有

type DataStreamItem = LinearAlgebra.Vector<float32>

type Ball =
    {R : float32;
     X : DataStreamItem}

并且我希望类型 DataStreamItem 的所有实例都具有 D 维度。

我的问题是为了算法开发和调试的利益，因为这种形状不匹配的错误可能令人头疼，但当算法正常运行时应该不是问题-运行 :

有没有办法，在 F# 或 Haskell 中，约束 DataStreamItem 和/或Ball 的维度是 D？或者我是否需要在每次计算时都求助于模式匹配？

如果是后者，是否有任何良好的轻量级范例可以在此类约束违规发生时立即捕获它们（并且在性能至关重要时可以将其删除）？

编辑：

澄清 D 受约束的意义：

D 的定义是，如果将函数 main(DataStream) 的算法表示为计算图，则所有中间计算都将取决于 D 的维度main(DataStream) 的执行。我能想到的最简单的例子是 M 与 DataStreamItem 的点积：DataStream 的维度将决定 M[=28 的维度参数的创建=]

另一个编辑：

一周后，我发现以下博客准确地概述了我在 Haskell 中寻找的依赖类型：

https://blog.jle.im/entry/practical-dependent-types-in-haskell-1.html

还有一个： R. Eisenberg 的 reddit contains some discussion on Dependent Types in Haskell and contains a link to the quite interesting dissertation proposal。

Answer 1

Haskell F# 类型系统都不足以（直接）表达“递归类型 T 的 N 个嵌套实例，其中 N 在 2 到 6 之间”或“一串恰好 6 长的字符”。至少不是那些确切的术语。

我的意思是，当然，您始终可以将这样的 6 长字符串类型表示为 type String6 = String6 of char*char*char*char*char*char 或某种变体（从技术上讲，这对于您使用向量的特定示例来说应该足够了，除非您没有告诉我们整个例子），但你不能说像 type String6 = s:string{s.Length=6} 这样的东西，更重要的是，你不能定义形式为 concat: String<n> -> String<m> -> String<n+m> 的函数，其中 n 和 m代表字符串长度。

但你不是第一个问这个问题的人。这个研究方向确实存在，叫做“dependent types”，我可以最笼统地表达它的要旨为“having higher-order, more类型 上的强大操作（与我们在 ML 语言中的联合和交集相反）——请注意在上面的示例中我如何使用数字而不是其他类型对类型 String 进行参数化，然后对该数字进行算术运算。

在这个方向上最突出的语言原型（据我所知）是 Agda, Idris, F*, and Coq（不是真正完整的 AFAIK）。检查它们，但要注意：这是明天的边缘，我不建议基于这些语言开始一个大项目。

(edit: 显然你 can do certain tricks in Haskell 模拟依赖类型，但它不是很方便，你必须启用 UndecidableInstances)

或者，您可以采用较弱的解决方案，即在运行时进行检查。一般要点是：将向量类型包装在普通包装器中，不允许直接构造它，而是提供构造函数，并使这些构造函数确保所需的属性（即长度）。类似于：

type Stream4 = private Stream4 of DataStreamItem
   with
      static member create (item: DataStreamItem) =
         if item.Length = 4 then Some (Stream4 item)
         else None

         // Alternatively:
         if item.Length <> 4 then failwith "Expected a 4-long vector."
         item

以下是 Scott Wlaschin 对方法的更完整解释：constrained strings。

Answer 2

所以如果我理解正确的话，你实际上并没有做任何类型级的算术运算，你只是有一个在函数调用链中共享的“长度标签”。

这在 Haskell 中早就可以做到；我认为非常优雅的一种方法是使用所需长度的标准固定长度类型来注释您的数组：

newtype FixVect v s = FixVect { getFixVect :: VU.Vector s }

为了确保正确的长度，您只提供（多态的）从固定长度类型构造的智能构造函数——非常安全，尽管没有提到实际的维数！

class VectorSpace v => FiniteDimensional v where
  asFixVect :: v -> FixVect v (Scalar v)

instance FiniteDimensional Float where
  asFixVect s = FixVect $ VU.singleton s
instance (FiniteDimensional a, FiniteDimensional b, Scalar a ~ Scalar b)        => FiniteDimensional (a,b) where
  asFixVect (a,b) = case (asFixVect a, asFixVect b) of
        (FixVect av, FixVect bv) -> FixVect $ av<>bv

这种未装箱元组的构造确实效率很低，但这并不意味着你可以用这种范式编写高效的程序——如果维度总是保持不变，你只需要包装和解包一次就可以完成所有的工作通过安全但运行时未经检查的拉链、折叠和 LA 组合进行关键操作。

无论如何，这种方法并没有真正广泛使用。也许单个常量维度实际上对于大多数相关操作来说太过局限，如果你需要经常解包成元组，那效率太低了。最近流行的另一种方法是实际用类型级别 numbers 标记向量。随着 GHC-7.4 中数据类型的引入，这些数字已经以可用的形式可用。到目前为止，它们仍然相当笨重，不适合正确的算术运算，但即将到来的 8.0 将在 Haskell.

中大大改进这种依赖类型编程的许多方面。

提供高效长度索引数组的库是 linear。

F# 和 Haskell 中向量维度的类型约束（依赖类型）

Type constraints on dimensionality of vectors in F# and Haskell (Dependent Types)

haskell

matrix

vector

f#

dependent-type