Haskell 98 中是否有可能出现无限类错误？

Question

我正在为一种新的函数式编程语言实现一个类系统，我目前正在编写函数来统一两种。有四种情况两人考虑：

+---------+---------+-------------------------------------------------------+
|   k1    |   k2    |                        action                         |
+=========+=========+=======================================================+
|   var   |   var   |                  k1 := k2 ^ k2 := k1                  |
+---------+---------+-------------------------------------------------------+
|   var   | non var |             if (!occurs(k1, k2)) k1 := k2             |
+---------+---------+-------------------------------------------------------+
| non var |   var   |             if (!occurs(k2, k1)) k2 := k1             |
+---------+---------+-------------------------------------------------------+
| non var | non var | ensure same name and arity, and unify respective args |
+---------+---------+-------------------------------------------------------+

当k1和k2都是变量时，它们会相互实例化。
当只有 k1 是一个变量时，它被实例化为 k2 当且仅当 k1 没有出现在 k2.
当只有 k2 是一个变量时，它被实例化为 k1 当且仅当 k2 没有出现在 k1.
否则检查k1和k2是否同名同元数，统一各自的参数。

对于第二种和第三种情况，我们需要实现发生检查，这样我们就不会陷入死循环。但是，我怀疑程序员是否能够构造出无限种。

在Haskell中构造无限类型很容易：

let f x = f

然而，无论我怎么努力，都无法构造出无限种。请注意，我没有使用任何语言扩展。

我问这个的原因是，如果根本不可能构造无限种类，那么我什至不会费心在我的种类系统中实现种类发生检查。

Answer 1

data F f = F (f F)

在 GHC 7.10.1 上，我收到消息：

kind.hs:1:17:
    Kind occurs check
    The first argument of ‘f’ should have kind ‘k0’,
      but ‘F’ has kind ‘(k0 -> k1) -> *’
    In the type ‘f F’
    In the definition of data constructor ‘F’
    In the data declaration for ‘F’

该消息并没有说它是一种无限类型，但它本质上就是发生检查失败时的情况。

Answer 2

另一个简单的例子

GHCi, version 7.10.1: http://www.haskell.org/ghc/  :? for help
Prelude> let x = undefined :: f f

<interactive>:2:24:
    Kind occurs check
    The first argument of ‘f’ should have kind ‘k0’,
      but ‘f’ has kind ‘k0 -> k1’
    In an expression type signature: f f
    In the expression: undefined :: f f
    In an equation for ‘x’: x = undefined :: f f

Haskell 98 中是否有可能出现无限类错误？

Is it possible to get the infinite kind error in Haskell 98?

ocaml

haskell

functional-programming

type-inference

unification