Haskell 中的列表是归纳的还是共归纳的?
Are Lists Inductive or Coinductive in Haskell?
所以我最近一直在阅读有关共归纳的内容,现在我想知道:Haskell 列表是归纳的还是共归纳的?我也听说 Haskell 不区分两者,但如果是,他们是如何正式区分的?
列表是归纳定义的,data [a] = [] | a : [a]
,但可以相互归纳使用,ones = a:ones
。我们可以创建无限列表。然而,我们可以创建有限列表。那么他们是谁?
相关的是在 Idris 中,其中类型 List a
严格来说是归纳类型,因此只是有限列表。它的定义类似于 Haskell 中的定义。然而,Stream a
是一个余归纳类型,模拟一个无限列表。它被定义为(或者更确切地说,定义等同于)codata Stream a = a :: (Stream a)
。不可能创建无限列表或有限流。但是,当我写下定义时
codata HList : Type -> Type where
Nil : HList a
Cons : a -> HList a -> HList a
我从 Haskell 列表中得到了我期望的行为,即我可以制作有限和无限结构。
所以让我将它们归结为几个核心问题:
Haskell不区分归纳类型和共归纳类型吗?如果是这样,那么形式化是什么?如果不是,那么哪个是[a]?
HList 是互推的吗?如果是这样,余归类型如何包含有限值?
如果我们定义data HList' a = L (List a) | R (Stream a)
呢?那会被认为是什么 and/or 它比 HList
有用吗?
由于懒惰,Haskell 类型既是归纳又是互归纳,或者说,data 和 codata 之间没有形式上的区别。所有递归类型都可以包含构造函数的无限嵌套。在 Idris、Coq、Agda 等语言中,像 ones = 1 : ones
这样的定义会被终止检查器拒绝。惰性意味着 ones
可以一步计算为 1 : ones
,而其他语言仅计算为范式,而 ones
没有范式。
'Coinductive' 并不表示 'necessarily infinite',它表示 'defined by how it is deconstructed',而归纳表示 'defined by how it is constructed'。我认为 this 是对细微差别的极好解释。您肯定会同意类型
codata A : Type where MkA : A
不能无限大。
这是一个有趣的 - 与 HList
相反,如果它是有限的或无限的,你永远无法 'know'(具体来说,你可以在有限的时间内发现如果一个列表是有限的,但你不能计算它是无限的),HList'
给你一个简单的方法来决定你的列表是有限的还是无限的。
在像 Coq 或 Agda 这样的全能语言中,归纳类型是那些其值可以在有限时间内被拆除的类型。归纳函数必须终止。另一方面,余积类型是那些其值可以在有限时间内 建立起来 的类型。余积函数必须是有效率的。
旨在用作证明助手的系统(如 Coq 和 Agda)必须 完整,因为非终止会导致系统在逻辑上不一致。但是要求所有函数都是完整的和归纳的,就不可能使用无限结构,因此发明了共归纳。
所以归纳和共归纳类型的目的是拒绝可能的非终止程序。这是 Agda 中的一个函数示例,该函数由于生产力条件而被拒绝。 (您传递给 filter
的函数可能会拒绝每个元素,因此您可能会永远等待结果流的下一个元素。)
filter : {A : Set} -> (A -> Bool) -> Stream A -> Stream A
filter f xs with f (head xs)
... | true = head xs :: filter f (tail xs)
... | false = filter f (tail xs) -- unguarded recursion
现在,Haskell 没有归纳或共归纳类型的概念。问题 "Is this type inductive or coinductive?" 不是一个有意义的问题。 Haskell怎么不区分就跑了?好吧,Haskell 一开始就没有打算作为逻辑保持一致。它是一种部分语言,这意味着您可以编写非终止和非生产性函数——没有终止检查器和生产率检查器。人们可以争论这一设计决策的智慧,但它肯定会使归纳和共归纳变得多余。
相反,Haskell 程序员习惯于 非正式地 推理程序的 termination/productivity。懒惰让我们使用无限的数据结构,但我们没有从机器那里得到任何帮助来确保我们的功能是完整的。
要解释类型级递归,需要找到一个 "fixed point"
CPO 值列表函子
F X = (1 + A_bot * X)_bot
如果我们归纳推理,我们希望不动点是"least"。如果互归纳,"greatest".
从技术上讲,这是通过在 CPO_bot 的嵌入投影子类别中工作来完成的,例如对于 "least" 嵌入图的余数
0_bot |-> F 0_bot |-> F (F 0_bot) |-> ...
推广 Kleene 不动点定理。对于"greatest",我们将采用投影图的极限
0_bot <-| F 0_bot <-| F (F 0_bot) <-| ...
然而,对于任何 F
,"least" 与 "greatest" 同构。这就是 "bilimit" 定理(参见 Abramsky 的 "Domain Theory" 调查论文)。
也许令人惊讶的是,归纳或共归纳的味道来自 F
而不是 least/greatest 固定点应用的提升。比如x
是被砸的产品,#
是被砸的金额,
F X = 1_bot # (A_bot x X)
将有限列表集作为双极限(最多 iso)。
[我希望我做对了——这些很棘手;-)]
所以我最近一直在阅读有关共归纳的内容,现在我想知道:Haskell 列表是归纳的还是共归纳的?我也听说 Haskell 不区分两者,但如果是,他们是如何正式区分的?
列表是归纳定义的,data [a] = [] | a : [a]
,但可以相互归纳使用,ones = a:ones
。我们可以创建无限列表。然而,我们可以创建有限列表。那么他们是谁?
相关的是在 Idris 中,其中类型 List a
严格来说是归纳类型,因此只是有限列表。它的定义类似于 Haskell 中的定义。然而,Stream a
是一个余归纳类型,模拟一个无限列表。它被定义为(或者更确切地说,定义等同于)codata Stream a = a :: (Stream a)
。不可能创建无限列表或有限流。但是,当我写下定义时
codata HList : Type -> Type where
Nil : HList a
Cons : a -> HList a -> HList a
我从 Haskell 列表中得到了我期望的行为,即我可以制作有限和无限结构。
所以让我将它们归结为几个核心问题:
Haskell不区分归纳类型和共归纳类型吗?如果是这样,那么形式化是什么?如果不是,那么哪个是[a]?
HList 是互推的吗?如果是这样,余归类型如何包含有限值?
如果我们定义
data HList' a = L (List a) | R (Stream a)
呢?那会被认为是什么 and/or 它比HList
有用吗?
由于懒惰,Haskell 类型既是归纳又是互归纳,或者说,data 和 codata 之间没有形式上的区别。所有递归类型都可以包含构造函数的无限嵌套。在 Idris、Coq、Agda 等语言中,像
ones = 1 : ones
这样的定义会被终止检查器拒绝。惰性意味着ones
可以一步计算为1 : ones
,而其他语言仅计算为范式,而ones
没有范式。'Coinductive' 并不表示 'necessarily infinite',它表示 'defined by how it is deconstructed',而归纳表示 'defined by how it is constructed'。我认为 this 是对细微差别的极好解释。您肯定会同意类型
codata A : Type where MkA : A
不能无限大。
这是一个有趣的 - 与
HList
相反,如果它是有限的或无限的,你永远无法 'know'(具体来说,你可以在有限的时间内发现如果一个列表是有限的,但你不能计算它是无限的),HList'
给你一个简单的方法来决定你的列表是有限的还是无限的。
在像 Coq 或 Agda 这样的全能语言中,归纳类型是那些其值可以在有限时间内被拆除的类型。归纳函数必须终止。另一方面,余积类型是那些其值可以在有限时间内 建立起来 的类型。余积函数必须是有效率的。
旨在用作证明助手的系统(如 Coq 和 Agda)必须 完整,因为非终止会导致系统在逻辑上不一致。但是要求所有函数都是完整的和归纳的,就不可能使用无限结构,因此发明了共归纳。
所以归纳和共归纳类型的目的是拒绝可能的非终止程序。这是 Agda 中的一个函数示例,该函数由于生产力条件而被拒绝。 (您传递给 filter
的函数可能会拒绝每个元素,因此您可能会永远等待结果流的下一个元素。)
filter : {A : Set} -> (A -> Bool) -> Stream A -> Stream A
filter f xs with f (head xs)
... | true = head xs :: filter f (tail xs)
... | false = filter f (tail xs) -- unguarded recursion
现在,Haskell 没有归纳或共归纳类型的概念。问题 "Is this type inductive or coinductive?" 不是一个有意义的问题。 Haskell怎么不区分就跑了?好吧,Haskell 一开始就没有打算作为逻辑保持一致。它是一种部分语言,这意味着您可以编写非终止和非生产性函数——没有终止检查器和生产率检查器。人们可以争论这一设计决策的智慧,但它肯定会使归纳和共归纳变得多余。
相反,Haskell 程序员习惯于 非正式地 推理程序的 termination/productivity。懒惰让我们使用无限的数据结构,但我们没有从机器那里得到任何帮助来确保我们的功能是完整的。
要解释类型级递归,需要找到一个 "fixed point" CPO 值列表函子
F X = (1 + A_bot * X)_bot
如果我们归纳推理,我们希望不动点是"least"。如果互归纳,"greatest".
从技术上讲,这是通过在 CPO_bot 的嵌入投影子类别中工作来完成的,例如对于 "least" 嵌入图的余数
0_bot |-> F 0_bot |-> F (F 0_bot) |-> ...
推广 Kleene 不动点定理。对于"greatest",我们将采用投影图的极限
0_bot <-| F 0_bot <-| F (F 0_bot) <-| ...
然而,对于任何 F
,"least" 与 "greatest" 同构。这就是 "bilimit" 定理(参见 Abramsky 的 "Domain Theory" 调查论文)。
也许令人惊讶的是,归纳或共归纳的味道来自 F
而不是 least/greatest 固定点应用的提升。比如x
是被砸的产品,#
是被砸的金额,
F X = 1_bot # (A_bot x X)
将有限列表集作为双极限(最多 iso)。
[我希望我做对了——这些很棘手;-)]