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 :: (* -> *) -> *

type 构造函数 Fix 类似于函数 fix.

data 构造函数是另外一回事。根据 Understanding F-Algebras 中的解释，Fix 是一个 求值器 ：它对类型 f (Fix f) 的项进行求值以产生类型 [=16] 的值=].本次评价无损；您可以使用 unFix.

从结果中恢复原始值

Answer 2

让我们采用 fix 的简单实现：

fix f = f (fix f)

对于函数 f，这将创建如下内容：

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

Fix newtype 做同样的事情，但对于类型。因此，如果我们采用 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

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

How the type `Fix` and function `fix` are same in Haskell?

haskell

recursion

fixpoint-combinators