我正在尝试将这个 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
有人知道这里发生了什么吗?
最佳答案
在自我申请d d
, d
既是函数,又是某种类型的a -> r
及其参数,类型为 a
.因此这两种类型必须是相同的,a ~ (a -> r)
.
Haskell 想要完全预先知道它的类型,所以它不断地用一个替换另一个,最终得到一个无限类型。
Haskell 中不允许使用无限类型,但允许使用递归类型。
我们在这里需要做的就是命名该递归类型:
newtype T r = D { app :: T r -> r }
现在T r
既是函数类型又是其参数,对于某些结果类型 r
.这里
T
是一个类型构造函数,D
它的数据构造函数,D :: (T r -> r) -> T r
.上面的记录语法定义了一个新的数据类型(这里虽然使用关键字
newtype
,而不是 data
)并将其单个字段命名为 app
.它还定义了 app
作为访问函数,app :: T r -> (T r -> r)
. (它是 D
的一种倒数,并且经常看到以“un”为前缀命名的此类函数,例如 app
本来可以命名为 unD
。但这里 app
是有道理的,我们将看到之后。)对于值
x
类型 T r
, x :: T r
,这意味着 x
是/匹配/某个值D g
在哪里 (g = app x) :: T r -> r
,即 app
简单地解开数据构造函数D
获得基础值(value)(一个函数)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 }
关于错误,第二种错误you get ,
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)
| ^
似乎比您所包含的更中肯/有用/。
关于javascript - 将定点运算符翻译成 Haskell 语言,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68975627/