将JS不动点算子翻译为Haskell时出现类型错误求助

Haskell 采用的 Hindley-Milner 类型系统默认不支持隐式递归类型，你编写的代码中存在自应用逻辑 x x，这要求参数 x 的类型同时满足 T 和 T -> U，属于无限递归类型，没有显式声明的情况下编译器无法自动推导，因此抛出类型变量逃逸的报错。而 JavaScript 是动态类型语言，编译期不做严格的静态类型校验，因此可以直接运行自应用逻辑。

你可以通过显式声明递归的 newtype 来绕开类型限制，newtype 仅作用于编译期的类型检查，运行时无额外开销，实现代码如下：

-- 定义递归类型包装自应用逻辑
newtype Func a b = Func { apply :: Func a b -> (a -> b) }

fix' :: ((a -> b) -> (a -> b)) -> (a -> b)
fix' f = d d
  where
    d x = f (\t -> apply x x t)

如果你不需要完全对齐JS的实现逻辑，也可以直接使用 Haskell 标准库Data.Function中内置的不动点算子fix，它的实现逻辑如下：

fix :: (a -> a) -> a
fix f = let x = f x in x

针对你需要的一元函数不动点场景，直接传入对应高阶函数即可正常使用。

内容的提问来源于stack exchange，提问作者F. Zer