我有一个向量数据类型,它是长度索引的
data Vector :: Nat -> Type -> Type where
VNil :: Vector 0 a
VCons :: a -> Vector n a -> Vector (n + 1) a
现在我想做的是,列表中的每个元素都包含一个类型为a
到b
的函数,但该类型b
对于向量中的每个索引都是不同的。
hMap :: forall n a. Vec n (forall b. a -> b) -> a -> Vec n (forall b. b)
hMap VNil _ = VNil
hMap (f `VCons` fs) a = f a `VCons` hMap fs a
当然这是不可能编译的。因为GHC不支持非 predicate 类型。有什么变通办法吗?也许是某种高压电除尘器我对这些高级特性不是很熟悉,但我真的很想知道hMap
是如何实现的。
感谢您的帮助!
1条答案
按热度按时间yh2wf1be1#
你定义的向量类型,正如你已经指出的,是同构的。你不能真正使用
forall
将同构类型转换为异构类型,因为这不是它的真正用途。相反,我们真正需要的是一个异构的向量类型。首先,让我们把形式摆在一边。我们将需要一个 * 很多 * 的GHC扩展到这结束时,所以在这里,我们去。
我假设您使用的
Nat
类型来自GHC.TypeLits
,而Type
类型来自Data.Kind
。现在你的原始向量类型看起来像这样。
我提议用这个代替。
而不是有一个 * 单一 * 类型的元素,我们有一个元素类型的列表。请注意,
xs
是类型(从Data.Kind
到Type
)的列表(如内置的[]
类型)。Haskell中定义的每一个类型都可以提升到类型级别。你已经看到了如何提升自然数的字面量(这是一个特殊的情况,因为它们周围的特殊语法),但我们可以对列表做同样的事情。VNil
只对长度为零和空类型列表有效,而VCons
对长度为n + 1
的 * 非空 * 列表有效,并且由元素t
(类型级别列表t ': ts
的头部)和尾部Vector n ts
组成。在构造函数的前面有撇号,我们正在从值级别提升到类型级别。
'[]
只是值构造器[]
(即空列表)提升到类型级别。在没有引号的情况下,在类型上下文中,[]
是* -> *
类型的类型构造函数,因此我们必须提升它以修复二义性。这样做通常是很好的做法,即使它不是模棱两可的。我还将
VCons
定义为在中缀形式中使用时是右结合的,这将使实际构建这些向量 * 稍微 * 容易一些。现在,我建议我们完全忽略
n
参数。你可以用n
参数做我在这里建议的几乎所有事情,但是因为我们也有列表,我们仍然知道我们的向量静态地有多长。所以我建议我们可以使用类型级函数恢复类型级的长度。实际上,这将是
hMap
的一个很好的实践,所以让我们把它写出来。当我们想写一个递归一个复杂的GADT类型的函数时,我们通常是这样做的,作为一个类型类。在本例中,我们需要一个名为
VectorLength
的类型级函数,因此我们将编写一个定义type family的类型类来给予我们结果。在普通值级别的Haskell中,您编写类型签名,然后编写要进行模式匹配的case。我们在类型级Haskell中做同样的事情。然而,我们的“类型签名”是
class
,我们的case是instance
s。这是我们的签名现在我们的基本情况是空列表类型级别值
'[]
的示例。把这句话再读一遍,确保你明白我在这里重载了什么。最后是递归的例子。
如果尾部(包含
xs
)有长度,则包含(x ': xs)
的向量有长度。具体来说,长度是1 + VectorLength xs
。您可以将示例的上下文(本例中为HasLength xs
)视为函数的一种依赖列表。我们的函数需要调用VectorLength xs
,所以我们必须在instance
头文件中声明。现在让我们写
hMap
。这也将在类型类中,但它将是一个常规的Haskell函数,而不是类型家族,因为我们希望在值级别上操作。它仍然必须是一个类型类,因为我们要在类型级别(即我们的组成类型列表)上进行 * 分派 *。这是类型签名
竖线
|
后面的那个有趣的小语法叫做functional dependency,它确实有助于类型推断。如果我知道fs
的值(函数),那么我可以推导出bs
的值(这些函数的结果)。现在我们来写一个基本案例。
空的函数列表可以被
hMap
填充到空的结果列表中,中间的类型a
无关紧要。具体来说,这个Map将VNil
Map到VNil
。继续我们的递归案例。
如果我们可以使用
a
类型的输入将fs
转换为bs
,那么我们也可以使用a
类型的输入将((a -> b) ': fs)
转换为(b ': bs)
。这里的巧妙之处在于,在完成了所有疯狂的类型级别的杂耍之后,函数体实际上非常简单和美丽。
我们来测试一下。这里有一些功能。
这就是为什么我在前面声明了
infixr
声明:所以我们可以在这里链接VCons
调用。下面是我们将这些函数应用于
0
时的结果列表。这是一种技术,但它有效吗?为了解决这个问题,我们需要编写一些快速的
Show
示例来打印它们。最后
判决结果呢
成功啦!
您可以在Try it online上看到此代码的完整工作示例!