"all (==1) [1,1..]" 不终止的数学意义是什么?
What is the mathematical significance of "all (==1) [1,1..]" not terminating?
直觉上,我希望 "mathematical" 对 all (==1) [1,1..]
的回答是 True
,因为列表中仅包含 1 的所有元素都等于 1。但是我理解"computationally",为了检查每个元素实际上是否等于 1 而计算无限列表的过程永远不会终止,因此表达式改为 "evaluates" 到底部或 ⊥
。
我觉得这个结果违反直觉,有点令人不安。我认为列表是无限的这一事实在数学和计算上混淆了这个问题,我很想听听任何在这方面有一些见解和经验的人的意见
我的问题是,哪个是数学上最正确的答案? ⊥
还是 True
?
关于为什么一个答案比另一个答案更正确的一些详细说明也将不胜感激。
编辑:这可能间接与Curry-Howard isomorphism (Programs are proofs and types are theorems) and Gödel's incompleteness theorems有关。如果我没记错的话,其中一个不完备性定理可以(难以置信的粗略)概括为"sufficiently powerful formal systems (like mathematics or a programming language) cannot prove all true statements that can be expressed in the system"
我对可计算性了解不够,无法正确回答这个问题,但我确实从语言设计的简单性中得到安慰。在这种情况下,我发现 all
不需要知道它给出的输入的任何信息,这简单而优雅。人们可以更容易地推理出您提供的片段。
当然,现在无限列表理解以某种方式告诉 all
它是一个无限列表会很好。但是……就是这么说的 "by being of that value"。拥有更多关于重复序列的通用元数据对于优化目的来说会更成功,但我认为会降低简单性,并引入复杂性。
价值
all (==1) [1,1..]
是序列的最小上界
all (==1) (⊥)
all (==1) (1 : ⊥)
all (==1) (1 : 1 : ⊥)
...
而这个数列的所有项都是⊥,所以最小上界也是⊥。 (所有 Haskell 函数都是连续的:保留最小上限。)
这是对 Haskell 使用 denotational semantics 并且不(直接)依赖于选择任何特定的评估策略。
在编程中,我们使用的不是经典逻辑,而是直觉(构造)逻辑。我们仍然可以将类型解释为定理,但我们不关心这些定理的真理;相反,我们讨论它们是否 可建设性证明 。尽管 all (== 1) [1, 1 ..]
是 true,但我们无法 证明 Haskell,所以我们得到 ⊥(这里,无限循环)。
在构造逻辑中,我们没有排中律,结果也没有双重否定消除法。 Haskell 函数类型 all (== 1) :: [Int] -> Bool
不代表定理 [Int] → Bool,这将是一个总函数;它代表定理 [Int] → ¬¬Bool。如果 all
可以通过产生结果来证明定理,那么该结果将是 Bool
类型;否则,结果是底部。
直觉上,我希望 "mathematical" 对 all (==1) [1,1..]
的回答是 True
,因为列表中仅包含 1 的所有元素都等于 1。但是我理解"computationally",为了检查每个元素实际上是否等于 1 而计算无限列表的过程永远不会终止,因此表达式改为 "evaluates" 到底部或 ⊥
。
我觉得这个结果违反直觉,有点令人不安。我认为列表是无限的这一事实在数学和计算上混淆了这个问题,我很想听听任何在这方面有一些见解和经验的人的意见
我的问题是,哪个是数学上最正确的答案? ⊥
还是 True
?
关于为什么一个答案比另一个答案更正确的一些详细说明也将不胜感激。
编辑:这可能间接与Curry-Howard isomorphism (Programs are proofs and types are theorems) and Gödel's incompleteness theorems有关。如果我没记错的话,其中一个不完备性定理可以(难以置信的粗略)概括为"sufficiently powerful formal systems (like mathematics or a programming language) cannot prove all true statements that can be expressed in the system"
我对可计算性了解不够,无法正确回答这个问题,但我确实从语言设计的简单性中得到安慰。在这种情况下,我发现 all
不需要知道它给出的输入的任何信息,这简单而优雅。人们可以更容易地推理出您提供的片段。
当然,现在无限列表理解以某种方式告诉 all
它是一个无限列表会很好。但是……就是这么说的 "by being of that value"。拥有更多关于重复序列的通用元数据对于优化目的来说会更成功,但我认为会降低简单性,并引入复杂性。
价值
all (==1) [1,1..]
是序列的最小上界
all (==1) (⊥)
all (==1) (1 : ⊥)
all (==1) (1 : 1 : ⊥)
...
而这个数列的所有项都是⊥,所以最小上界也是⊥。 (所有 Haskell 函数都是连续的:保留最小上限。)
这是对 Haskell 使用 denotational semantics 并且不(直接)依赖于选择任何特定的评估策略。
在编程中,我们使用的不是经典逻辑,而是直觉(构造)逻辑。我们仍然可以将类型解释为定理,但我们不关心这些定理的真理;相反,我们讨论它们是否 可建设性证明 。尽管 all (== 1) [1, 1 ..]
是 true,但我们无法 证明 Haskell,所以我们得到 ⊥(这里,无限循环)。
在构造逻辑中,我们没有排中律,结果也没有双重否定消除法。 Haskell 函数类型 all (== 1) :: [Int] -> Bool
不代表定理 [Int] → Bool,这将是一个总函数;它代表定理 [Int] → ¬¬Bool。如果 all
可以通过产生结果来证明定理,那么该结果将是 Bool
类型;否则,结果是底部。