haskell - Haskell 中的类型 `Fix` 和函数 `fix` 是如何相同的？

Question

我试图说服自己类型Fix和功能fix是一回事。
但我找不到他们的定义之间的相关性

-- definition of fix 
fix :: (p -> p) -> p
fix f = let {x = f x} in x -- or fix f = f (fix f)
-- definition of Fix
newtype Fix f = Fix { unFix :: f (Fix f) }

构造函数如何Fix适应 的形式(x -> x) -> x？

Answer 1

查看类型构造函数的种类Fix：

> :k Fix
Fix :: (* -> *) -> *

类型构造函数Fix类似于函数fix。

数据构造函数是另一回事。遵循Understanding F-Algebras中的解释，Fix是一个评估器：它评估一个类型的项f (Fix f)以产生一个类型的值Fix f。这个评价是无损的；您可以使用 . 从结果中恢复原始值unFix。

Answer 2

让我们以天真的实现为例fix：

fix f = f (fix f)

对于一个函数f，这会创建如下内容：

f (f (f (f (f (f (f ...

Fixnewtype 做同样的事情，但对于类型。因此，如果我们采用 type Maybe，我们将要创建：

Maybe (Maybe (Maybe (Maybe (Maybe (Maybe ...

我们将如何创建一个构造该类型的函数？我们可以先尝试使用类型同义词：

--   fix f = f (fix f)
type Fix f = f (Fix f)

您应该能够看到这与fix上面的幼稚实现相同，只是做了一些小的改动。但这不是合法的 Haskell！

这有很多原因：主要是，Haskell 不允许像Maybe上面的例子那样无限类型，而且 Haskell 的类型系统是严格的，与fix. 这就是为什么我们需要一个newtype. 新类型定义（使用newtypeor引入data）允许递归，因此我们采用类型同义词并将其更改为新类型。

type    Fix f =                f (Fix f)
newtype Fix f =                f (Fix f)   -- change to newtype
newtype Fix f = Fix           (f (Fix f))  -- need to have a constructor
newtype Fix f = Fix { unFix :: f (Fix f) } -- And name the field, also