可以使用 Haskell 列表中的单例 Nats（如 0、1、...）制作一个大小列表吗？

Question

在学习单例和（半）依赖类型时，我开始尝试从一个正常的 Haskell 列表中创建一个大小列表，其中大小由 Nats 给出，例如 0, 1, 2, 3,.. . 而不是 Z、S Z、S (S Z) 等。顺便说一句，我正在使用 Data.Singletons.TypeLits 库。 (singletons-2.5.1).

这是我一直在尝试的方法：

data NatList (a :: *) (n :: Nat) where
    Nah :: NatList a 0
    Yea :: a -> NatList a n -> NatList a (n + 1)

fromList :: SNat n -> [a] -> NatList a n
fromList s []     = Nah
fromList s (x:xs) = Yea x (fromList (s %- (SNat :: SNat 1)) xs)

此代码无法编译并给我一个错误

“无法将类型‘n’与‘0’匹配 ‘n’ 是一个严格的类型变量，由类型签名： fromList::forall(n::Nat) a． SNat n -> [a] -> NatList a n

Answer 1

我不知道那个库，但据我了解，问题似乎出在 fromList 的第一个子句中，它应该只在 n=0 时匹配。

--...
fromList 0 []     = Nah
--...

Answer 2

你对 fromList 的签名说它适用于任何类型 n :: Nat。但是第一个方程 returns Nah，它要求 n 类型为 0.

所以 fromList 需要是一个 class 的方法，它可以在 n.

的类型上发送

但是您正试图将 value 的第二个参数发送给 fromList——也就是说，列表是否为空——a依赖型。 Singletons library/technique 是在 Haskell 中伪造依赖类型。这就是我的知识耗尽的地方。所以我将 Peano Nats S Z 与实例一起使用，而不是与 GADT 一起使用。

Answer 3

离开这个问题一段时间后，我回来找到了一个适合我的解决方案：对大小列表类型使用存在包装器并转换运行时列表

data SizedList (a :: *) (n :: Nat) where
    Nil  :: SizedList a 0
    Cons :: a -> SizedList a n -> SizedList a (n+1)

data SomeSL (a :: *) where
    MkSomeSL :: KnownNat n => SNat n -> SizedList a n -> SomeSL a  

toList :: SizedList a n -> [a]
toList Nil         = []
toList (Cons x xs) = x : toList xs

fromList :: [a] -> SomeSL a
fromList []     = MkSomeSL (SNat @0) Nil 
fromList (x:xs) = case (fromList xs) of 
    MkSomeSL n ys -> MkSomeSL (n %+ SNat @1) (Cons x ys)

toList_ :: SomeSL a -> [a]
toList_ (MkSomeSL _ xs) = toList xs

在这里，SomeSL 将我的问题中的 SizedList 类型与单例 nat 一起包装起来，允许函数通过 SNat n 访问长度。

Justin Le 关于单例的系列博文很有帮助：https://blog.jle.im/entry/introduction-to-singletons-1.html

可以使用 Haskell 列表中的单例 Nats（如 0、1、...）制作一个大小列表吗？

Can one make a sized list using singleton Nats (like 0, 1, ...) from Lists in Haskell?

haskell

dependent-type

type-level-computation

singleton-type