4

我正在尝试将这个 JS 定点运算符翻译成 Haskell。

JS：

const fix = F => {
    const D = X => F(
        t => X(X)(t)
    )
    return D(D)
};

我的尝试是（Haskell）：

fix' f = d d
  where
    d x = f (\t -> x x t)

但是，我收到以下错误：

Couldn't match expected type ‘(t2 -> t3) -> t4’
              with actual type ‘p’
because type variables ‘t2’, ‘t3’, ‘t4’ would escape their scope
These (rigid, skolem) type variables are bound by the inferred type of d :: (t1 -> t2 -> t3) -> t4

有人知道这里发生了什么吗？

4

1 回答 1

2

在自我应用程序d d中，d它既是某种类型的函数，又是某种类型a -> r的参数a。因此，这两种类型必须是一种且相同的，a ~ (a -> r)。

Haskell 想要完全预先知道它的类型，所以它不断地用一个替换另一个，最终得到一个无限类型。

Haskell 中不允许使用无限类型，但允许使用递归类型。

我们在这里需要做的就是命名该递归类型：

newtype T r = D { app :: T r -> r }

对于某些结果类型， NowT r既是函数的类型，又是它的参数r。

这T是一个类型构造函数D及其数据构造函数D :: (T r -> r) -> T r。

上面的记录语法定义了一个新的数据类型（这里虽然使用关键字newtype，not data）并将其单个字段命名为app. 它还定义app为访问器函数，app :: T r -> (T r -> r). （这有点D像_appunDapp

对于x类型T r,的值x :: T r，这意味着x/ 匹配 / 某个值D gwhere (g = app x) :: T r -> r，即app简单地打开数据构造函数D以获取底层值（一个函数）g：x = D g ; app x = app (D g) = g。这就是 Haskell 中记录语法的工作方式。

现在我们可以写

{- fix' f = d d
     where
       d x = f (\t -> x x t)   -- applying x to x can't be typed!
-}

fix1 :: ((t1 -> t) -> t1 -> t) -> t1 -> t
fix1 f = d (D d)
  where
    d x = f (\t -> app x x t)   -- `app`ing x to x is well-typed!

fix2 :: ((t1 -> t) -> t1 -> t) -> t1 -> t
fix2 f = d (D d)
  where
    d (D y) = f (\t -> y (D y) t)

fix3 :: ((t1 -> t) -> t1 -> t) -> t1 -> t
fix3 f = f (\t -> d (D d) t)
  where
    d (D y) = f (\t -> y (D y) t)

fix4 :: (t -> t) -> t
fix4 f = f (d (D d))
  where
    d (D y) = f (y (D y))

所有的工作。最后一个甚至与内置的类型相同fix。

但是 Haskell 不仅有递归类型。它本身也有递归。一个实体被允许在它自己的定义中引用它自己。

因此，正如评论所说，我们真的不需要通过自我应用作为参数传递的值来模拟递归。我们可以递归地使用被定义的函数本身：

fix0 :: (t -> t) -> t
fix0 f  =  f (fix0 f)

或者我们可以使用递归定义的值：

y :: (t -> t) -> t
y f  =  x  where  { x = f x }

关于错误，您得到的第二种错误，

prog.hs:3:22: error:
    • Occurs check: cannot construct the infinite type:
        t1 ~ t1 -> t2 -> t3
    • In the first argument of ‘x’, namely ‘x’
      In the expression: x x t
      In the first argument of ‘f’, namely ‘(\ t -> x x t)’
    • Relevant bindings include
        t :: t2 (bound at prog.hs:3:15)
        x :: t1 -> t2 -> t3 (bound at prog.hs:3:7)
        d :: (t1 -> t2 -> t3) -> t4 (bound at prog.hs:3:5)
  |
3 |     d x = f (\t -> x x t)
  |                      ^

似乎比您所包含的更中肯/有用/。

于 2021-08-29T20:19:06.940 回答