Luyu Cheng

Bottom Type in Haskell

Haskell
type-system
functional-programming

今天偶然遇到了一个奇怪的符号 \bot,仔细查找了一下才发现这是 Haskell 中的一个特殊类型的值,其作用是用于表达{发散项}^(divergent term),也可以理解为不可计算的项。我之前在《{类型与程序设计语言}^(Types and Programming Lanuages)》上见过这个词,感觉可以在这里解释,干脆就把原文引用过来。

Recall that a term that cannot take a step under the evaluation relation is called a normal form. Interestingly, some terms cannot be evaluated to a normal form. For example, the divergent combinator ω=(λx.xx)(λx.xx)\omega = (\lambda x. x x) (\lambda x. x x) contains just one redex, and reducing this redex yields exactly ω\omega again! Terms with no normal form are said to diverge.

至于为什么不能表达,Haskell Wiki 上的解释是如果可以表达这样的项,那么编译器就可以解决停机问题了(我感觉这个证明应该会比较简单,改天水一篇博客文章)。下面是 \bot 的一个常见定义。

bottom = bottom

因为它不断引用自身,所以在 GHCi 中打印 bottom 会进入死循环。手头有 GHCi 的读者可以试一下。同时,\bot 是可以转换为任何类型的,这一点上和 undefined 类似。