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。

该数据构造是另一回事。遵循在理解 F-代数中找到的解释，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. 新类型定义（用newtype或引入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