gpt4 book ai didi

list - 有限递归 "List"类型

转载 作者:行者123 更新时间:2023-12-04 22:57:25 25 4
gpt4 key购买 nike

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

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

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

这允许构建无限列表。是否有可能以某种方式定义一个列表类型,它只允许有限(但仍然是任意长度)列表?

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

最佳答案

备选方案 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)

以下使存在量化类型变量“转义” case 的作用域:
-- fails to compile
test3 :: MyList Int
test3 = MyList $ case test3 of
MyList list -> (Cons 1 list)

关于list - 有限递归 "List"类型,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44544214/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com