Bottom Type in Haskell

今天偶然遇到了一个奇怪的符号 $\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 $\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 类似。