在这篇博客文章https://blog.jle.im/entry/fixed-length-vector-types-in-haskell.html中,作者创建了一个依赖类型的向量Vec n a
。其中一个创建的函数是withVec :: [a] -> (forall n. Sing n -> Vec n a -> r) -> r
,它从列表中创建一个中间向量,并在其上应用一个函数。有没有办法为withVec
提供一个类似id的函数来提取中间向量?在这篇文章的评论中,它创建了一个sum :: Sing n -> Vec n Int -> Int
函数,但任何试图创建一个函数,它的结果是类型Vec n a
已经失败。在这个https://hackage.haskell.org/package/type-combinators-0.2.4.3/docs/Data-Type-Vector.html包中也没有一个fromList
函数,将创建一个Vec n a
从列表。为什么?我们不能创建一个编译时检查的fromList
函数来从长度为n的列表中创建适当的Vec a n
,这是有原因的吗?我已经尝试并成功地创建了一个fromList
函数,但它在运行时检查正确的长度,而不是在编译时。
2条答案
按热度按时间ttcibm8c1#
有没有办法给
withVec
提供一个类似id的函数来提取中间向量?不,
withVec
的类型是精心制作的,正是为了防止这种情况。旁注:在库中,这个“技巧”通常用于
runST
类型,以确保ST s
monad的安全性。任何尝试创建一个函数,它的结果是类型
Vec n a
已经失败。实际上,这在设计上是不可能的。
没有一个
fromList
函数可以从一个列表中创建一个Vec n a
。为什么?我们不能创建一个编译时检查的fromList
函数来从一个长度为n的列表中创建一个合适的Vec a n
,这是有原因的吗?一开始可能并不明显,但这在现实中并不可行。
假设我们有这样一个
fromList
,它的类型是什么?让我们猜一下:字符串
但这实际上意味着
型
所以它声称能够将任何列表转换为任何长度的任何向量。这不可能是合理的。
问题是
forall n
部分意味着fromList
的 * 调用者 * 可以选择n
。但是这样就不能保证n
是输入列表的长度,所以存在不匹配。我们可以尝试让
n
被fromList
选择,而不是被调用者选择。型
然而,这有两个后果。
首先,
exists n . Vec n a
是一个未知长度的向量类型,因此本质上同构于[a]
,使得fromList
不是很有用。第二,我们可以利用一种已知的编码来表示真实的Haskell中的存在类型,但这将是
型
它与
withVec
非常相似!(实际上withVec
比这个变体更有用。)另一种替代方法是类似于
型
这里,调用者必须(静态地)预测(动态地)列表的长度
n
。如果它是正确的,他们得到Just theVector
,否则他们得到Nothing
。这是否有用取决于我们是否可以在静态时正确地猜测n
。请注意,就我所知,
fromList
的最后一个变体似乎可以在给定withVec
的情况下实现。最后,在一种完全依赖类型的语言中,我们可以编写
型
但是Haskell没有真正的依赖类型(因为它的目标是为了效率而允许全类型擦除)。
mbjcgjjk2#
为什么函数不能将列表转换为向量?
字符串
应用于空列表,当唯一有意义的类型是
Vec 0 a
时,这会产生一个任意长度的向量fromList [] :: Vec n a
。你可以看到这是一个“某个长度 n”的向量,其中 n 是存在的(proposal)。没有依赖类型,我们不知道。型
这与
withVec
相同,withVec
使用CPS对存在性进行编码。唯一的区别是Sing n
:在运行时保留(不删除)长度。型
我不认为
exists.
有一个相关的名字已经决定了。它可以编码为一个数据类型。型
这样的存在式非常适合模式同义词,它允许你在普通列表上进行模式匹配并得到一个向量。我也在单例
Sing
上进行模式匹配,说我们静态地知道长度 n。有趣的是,当标识延续传递给
(
withVec\_ -> id)
时会发生什么。