编译时强制执行的有限列表

Question

我想创建一个类型来表示具有有限数量元素的列表。

现在最简单的方法是严格求值：

data FiniteList a
  = Nil
  | Cons a !(List a)

有了这个无限列表相当于底部。

但是我想要一个完全阻止创建此类列表的类型。理想情况下，我希望任何构建无限列表的尝试都会导致编译时错误。

如果我使用 GADTs 和 DataKinds.

构建大小列表，我可以开始了解如何完成此操作

data Natural = Zero | Succ Natural

data DependentList :: Natural -> Type -> Type where
  Nil  :: DependentList 'Zero a
  Cons :: a -> DependentList n a -> DependentList ('Succ n) a

如果我们尝试构建类似

的东西

a = Cons 1 a

我们收到类型错误，因为这需要类型 n ~ 'Succ n。

问题在于它不是单一列表类型，而是 class 类型，每种列表大小对应一个。因此，例如，如果我想在此列表中编写 take 或 drop 的版本，我将需要开始进行一些严重的依赖类型。

我想将所有这些独立的类型统一在一个类型下，该类型在编译时仍然强制执行有限性。

这可以做到吗？

Answer 1

这可以通过提供终止检查的 Liquid Haskell 来完成。
类型签名在 Liquid Haskell:

中看起来像这样

{-@ (function name) :: (refinement) [/ (termination metric)] @-}

终止度量是一个整数向量，应该减少每个递归调用（字典顺序）。如果未指定，LH 将使用第一个整数参数作为终止度量。
可以使用延迟注释禁用终止检查 {-@ lazy (function name) @-}:

{-@ lazy inf @-}
inf x = x : inf x

Answer 2

是的，只是用一个存在主义来忘记有限的长度：

data NonDependentList a where NonDependentList :: DependentList n a -> NonDependentList a

当然，take 和 drop 会有一些样板...

take :: Int -> NDL a -> NDL a
take n (NDL Nil) = NDL Nil
take n (NDL (Cons a as)) = case take (n-1) (NDL as) of
    NDL as' -> NDL (Cons a as')

但是你还是做不到无限的：

ones = NDL (Cons 1 (case ones of NDL os -> os)) -- existential escapes its scope

Answer 3

还有 "ghosts of departed proofs" 方法，它涉及一个带有仔细公开的智能构造函数的标记新类型，并以类型标记中的延续多态的延续传递样式工作：

{-# LANGUAGE DeriveFunctor, RankNTypes, RoleAnnotations #-} 
module FinList (FinList,empty,toFinList,cons) where 
-- FinList constructor should NOT be public, or else everything breaks!

newtype FinList name a = FinList { getFinList :: [a] } deriving Functor

-- Don't allow Data.Coerce.coerce to turn FinList X a into forall x. FinList x a
type role FinList nominal representational

empty :: forall a r. (forall name . FinList name a -> r) -> r
empty f = f (FinList [])

toFinList:: forall a r. Int -> [a] -> (forall name. FinList name a -> r) -> r
toFinList n as f = f (FinList (take n as))

cons :: forall a r name'. a -> FinList name' a -> (forall name. FinList name a -> r) -> r
cons a (FinList as) f = f (FinList (a:as))

这应该可以防止 FinList 模块的客户端创建循环定义。

编译时强制执行的有限列表

Compile time enforced finite lists

list

haskell

dependent-type