有限递归 "List" 类型

Question

在Haskell中重构列表类型很容易：

data MyList a = Cons a (MyList a)
               | Empty
               deriving (Show)

someList = Cons 1 (Cons 2 (Cons 3 Empty)) -- represents [1,2,3]

这允许构建无限列表。是否有可能以某种方式定义一个列表类型，它只允许 finite（但仍然是任意长度）列表？

此处的列表示例可以替换为任何其他可能无限的数据结构，例如树等。请注意，我没有考虑任何特定的应用程序，因此无需质疑它的用处，我是只是好奇这是否可能。

Answer 1

备选方案 1：带有严格尾部的列表

data MyList a = Cons a !(MyList a) | Empty

试图构建一个无限列表肯定会导致底部元素 MyList a。

备选方案2：存在量化定长列表

data Nat = O | S Nat
data List a (n :: Nat) where
   Nil :: List a O
   Cons :: a -> List a n -> List a (S n)
data MyList a where
   MyList :: List a n -> MyList a

我会说这也不允许无限列表。

这是因为我们无法在具有 where（或一般惰性模式）的 GADT 上进行模式匹配。

-- fails to compile
test :: MyList Int
test = MyList (Cons 1 list)
       where MyList list = test

以下太严格了。

-- diverges
test2 :: MyList Int
test2 = case test2 of
          MyList list -> MyList (Cons 1 list)

下面使存在量化类型变量"escape"成为case的范围：

-- fails to compile
test3 :: MyList Int
test3 = MyList $ case test3 of
          MyList list -> (Cons 1 list)

有限递归 "List" 类型

finite recursive "List" type

haskell

list

infinite

备选方案 1：带有严格尾部的列表

备选方案2：存在量化定长列表