我如何构建一个具有独立类型长度的列表？ [英] How do I build a list with a dependently-typed length?
问题描述
<$> c $ c> { - ＃LANGUAGE DataKinds，GADTs，KindSignatures＃ - }
- 一种声明
数据Nat = Z | S Nat
SafeList ::（Nat - > * - > *）其中
Nil :: SafeList Z a
缺点:: a - > SafeList n a - > SafeList（S n）a
- 类型签名确保输入列表至少包含一个元素
safeHead :: SafeList（S n）a - > a
safeHead（Cons x xs）= x
这似乎起作用：
ghci> ：t缺点5（缺点3无）
缺点5（缺点3无）:: Num a => SafeList（'S（'S'Z））a
ghci> safeHead（Cons'x'（Cons'c'Nil））
'x'
ghci> safeHead无
无法匹配类型'Z'与'S n0
预期类型：SafeList（'S n0）a0
实际类型：SafeList'Z a0
在第一个参数'safeHead'，即`Nil'
在表达式中：safeHead Nil
在'it'的等式中：it = safeHead Nil
然而，为了使这个数据类型实际上有用，我应该能够从运行时数据中构建它，但您不知道它的长度编译时间。我天真的尝试：
fromList :: [a] - > SafeList na
fromList = foldr Cons Nil
无法编译，错误类型为：
无法匹配类型'Z'和'S n
预期类型：a - > SafeList n a - > SafeList n a
实际类型：a - > SafeList n a - > SafeList（'S n）a
在'foldr'的第一个参数中，即'Cons'
在表达式中：foldr Cons Nil
在`fromList'的等式中：fromList = foldr缺点
我明白为什么会发生这种情况： Cons的返回类型对于每次迭代都是不同的 - 这就是整个点！但是我看不到解决方法，可能是因为我没有深入阅读这个主题。 （我无法想象所有这些努力都被放入了一个实践中不可能使用的类型系统中！）
所以：我该如何建立这种依赖关系从'普通的'简单类型的数据的类型数据？
继@ luqui的建议，我能够使 fromList compile：
data ASafeList a where
ASafeList :: SafeList na - > ASafeList a
fromList :: [a] - > ASafeList a
fromList = foldr f（ASafeList Nil）
其中fx（ASafeList xs）= ASafeList（Cons x xs）
以下是我尝试解开 ASafeList 并使用它：
getSafeHead :: [a] - > a
getSafeHead xs =来自ASafeList的xs的case ys - > safeHead ys
这会导致另一种类型的错误：
< pre $ 无法与'n'类型匹配'S n0
'n'是一个刚性类型变量，由$ b $绑定$ b模式，带有构造函数
ASafeList： ：forall a（n :: Nat）。 SafeList n a - > ASafeList a，
（在SafeList.hs中为
）：
预期类型：SafeList（'S n0）a
实际类型：SafeList na
在`safeHead'的第一个参数中，即'ys'
在表达式中：safeHead ys
在一个替代方案中：ASafeList ys - > safeHead ys
再说一遍，直观地说，这是无法编译的。我可以用空列表调用 fromList ，所以编译器不能保证我能够调用 safeHead 在产生的 SafeList 上。这种缺乏知识大致是存在的 ASafeList 捕获的。
这个问题能解决吗？我觉得我可能已经走下了一条逻辑死胡同。
永远不要抛弃任何东西。
$ b
如果您不费吹灰之力就可以创建一个长度索引列表（在文献中称为矢量），那么您最好记住它的长度。
因此，我们有
数据Nat = Z | S Nat
数据Vec :: Nat - > * - > *哪里 - 旧习惯难以消除
VNil :: Vec Z a
VCons :: a - > Vec n a - > Vec（S n）a
但我们也可以给出静态长度的运行时间表示。理查德·艾森伯格的单身人士套餐将为你做到这一点，但基本的想法是为静态数字提供一种类型的跑步时间表示形式。
数据Natty :: Nat - > *其中
Zy :: Natty Z
Sy :: Natty n - >至关重要的是，如果我们有一个类型的值<纳蒂n ，那么我们可以询问该值以找出 n 是什么。
Hasochist知道运行时可代表性通常很无聊，甚至一台机器也可以管理它，所以我们把它隐藏在一个类型类中
类NATTY（n :: Nat）其中
natty :: Natty n
实例NATTY Z其中
natty = Zy
实例NATTY n => ; NATTY（S n）其中
natty = Sy natty
现在我们可以给出稍微更多
数据LenList :: * - > *其中
LenList :: NATTY n => Vec n a - > LenList a
lenList :: [a] - > LenList a
lenList [] = LenList VNil
lenList（x：xs）= case LenList xs LenList ys - > LenList（VCons x ys）
您获得与破坏长度的版本相同的代码，但您可以你可以随时随地获得长度的运行时间表示，并且你不需要沿着矢量抓取它。
当然，如果你想要长度成为一个 Nat ，对于某些，你仍然有一个痛苦，那就是你有一个 Natty n
$ b 这是一个错误，编辑我想补充一点，以解决安全头使用问题。
首先，让我为<$ c添加一个解包器
$ b $ $ $ $ $ $ $ $ $ $ unLenList :: LenList a - $ c $ Len $ $ c $ Len $ > （全部n代表n - > n代表 - > t） - > t
unLenList（LenList xs）k = k natty xs
现在假设我定义了
vhead :: Vec（S n）a - > a
vhead（VCons a _）= a
执行安全属性。如果我有运行时间表示矢量的长度，我可以看看它是否适用 vhead 。
headOrBust :: LenList a - >可能是
headOrBust lla = unLenList lla $ \ n xs - >案例n的
Zy - > Nothing
Sy _ - >只是（vhead xs）
所以你看一件事，然后学习另一件事。
Dipping my toe into the waters of dependent types, I had a crack at the canonical "list with statically-typed length" example.
{-# LANGUAGE DataKinds, GADTs, KindSignatures #-}
-- a kind declaration
data Nat = Z | S Nat
data SafeList :: (Nat -> * -> *) where
Nil :: SafeList Z a
Cons :: a -> SafeList n a -> SafeList (S n) a
-- the type signature ensures that the input list has at least one element
safeHead :: SafeList (S n) a -> a
safeHead (Cons x xs) = x
This seems to work:
ghci> :t Cons 5 (Cons 3 Nil)
Cons 5 (Cons 3 Nil) :: Num a => SafeList ('S ('S 'Z)) a
ghci> safeHead (Cons 'x' (Cons 'c' Nil))
'x'
ghci> safeHead Nil
Couldn't match type 'Z with 'S n0
Expected type: SafeList ('S n0) a0
Actual type: SafeList 'Z a0
In the first argument of `safeHead', namely `Nil'
In the expression: safeHead Nil
In an equation for `it': it = safeHead Nil
However, in order for this data-type to be actually useful, I should be able to build it from run-time data for which you don't know the length at compile time. My naïve attempt:
fromList :: [a] -> SafeList n a
fromList = foldr Cons Nil
This fails to compile, with the type error:
Couldn't match type 'Z with 'S n
Expected type: a -> SafeList n a -> SafeList n a
Actual type: a -> SafeList n a -> SafeList ('S n) a
In the first argument of `foldr', namely `Cons'
In the expression: foldr Cons Nil
In an equation for `fromList': fromList = foldr Cons Nil
I understand why this is happening: the return type of Cons is different for each iteration of the fold - that's the whole point! But I can't see a way around it, probably because I've not read deeply enough into the subject. (I can't imagine all this effort is being put into a type system that is impossible to use in practice!)
So: How can I build this sort of dependently-typed data from 'normal' simply-typed data?
Following @luqui's advice I was able to make fromList compile:
data ASafeList a where
ASafeList :: SafeList n a -> ASafeList a
fromList :: [a] -> ASafeList a
fromList = foldr f (ASafeList Nil)
where f x (ASafeList xs) = ASafeList (Cons x xs)
Here's my attempt to unpack the ASafeList and use it:
getSafeHead :: [a] -> a
getSafeHead xs = case fromList xs of ASafeList ys -> safeHead ys
This causes another type error:
Couldn't match type `n' with 'S n0
`n' is a rigid type variable bound by
a pattern with constructor
ASafeList :: forall a (n :: Nat). SafeList n a -> ASafeList a,
in a case alternative
at SafeList.hs:33:22
Expected type: SafeList ('S n0) a
Actual type: SafeList n a
In the first argument of `safeHead', namely `ys'
In the expression: safeHead ys
In a case alternative: ASafeList ys -> safeHead ys
Again, intuitively it makes sense that this would fail to compile. I can call fromList with an empty list, so the compiler has no guarantee that I'll be able to call safeHead on the resulting SafeList. This lack of knowledge is roughly what the existential ASafeList captures.
Can this problem be solved? I feel like I might have walked down a logical dead-end.
Never throw anything away.
If you're going to take the trouble to crank along a list to make a length-indexed list (known in the literature as a "vector"), you may as well remember its length.
So, we have
data Nat = Z | S Nat
data Vec :: Nat -> * -> * where -- old habits die hard
VNil :: Vec Z a
VCons :: a -> Vec n a -> Vec (S n) a
but we can also give a run time representation to static lengths. Richard Eisenberg's "Singletons" package will do this for you, but the basic idea is to give a type of run time representations for static numbers.
data Natty :: Nat -> * where
Zy :: Natty Z
Sy :: Natty n -> Natty (S n)
Crucially, if we have a value of type Natty n, then we can interrogate that value to find out what n is.
Hasochists know that run time representability is often so boring that even a machine can manage it, so we hide it inside a type class
class NATTY (n :: Nat) where
natty :: Natty n
instance NATTY Z where
natty = Zy
instance NATTY n => NATTY (S n) where
natty = Sy natty
Now we can give a slightly more informative existential treatment of the length you get from your lists.
data LenList :: * -> * where
LenList :: NATTY n => Vec n a -> LenList a
lenList :: [a] -> LenList a
lenList [] = LenList VNil
lenList (x : xs) = case lenList xs of LenList ys -> LenList (VCons x ys)
You get the same code as the length-destroying version, but you can grab a run time representation of the length anytime you like, and you don't need to crawl along the vector to get it.
Of course, if you want the length to be a Nat, it's still a pain that you instead have a Natty n for some n.
It's a mistake to clutter one's pockets.
Edit I thought I'd add a little, to address the "safe head" usage issue.
First, let me add an unpacker for LenList which gives you the number in your hand.
unLenList :: LenList a -> (forall n. Natty n -> Vec n a -> t) -> t
unLenList (LenList xs) k = k natty xs
And now suppose I define
vhead :: Vec (S n) a -> a
vhead (VCons a _) = a
enforcing the safety property. If I have a run time representation of the length of a vector, I can look at it to see if vhead applies.
headOrBust :: LenList a -> Maybe a
headOrBust lla = unLenList lla $ \ n xs -> case n of
Zy -> Nothing
Sy _ -> Just (vhead xs)
So you look at one thing, and in doing so, learn about another.
这篇关于我如何构建一个具有独立类型长度的列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
