fix 只能用非严格评估的语言输入吗？

Question

我在 Javascript 中和为 Javascript 编写了一个运行时类型检查器，但无法键入 fix:

fix :: (a -> a) -> a
fix f = ...

fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5 -- 120

传递给 fix 的阶乘函数具有简化类型 (Int -> Int) -> Int -> Int。

当我尝试重现 Javascript 中的表达式时，我的类型检查器因无效约束 Int ~ Int -> Int 而失败。

fix (const "hallo") 也失败了，类型检查器抱怨说它不能构造一个无限类型（负发生检查）。

对于其他组合器，我的统一结果与 Haskell 一致。

我的统一算法可能是错误的还是fix只能在非严格环境中输入？

[编辑]

我在 Javascript 中对 fix 的实现是 const fix = f => f(f)。

Answer 1

这是类型检查器中的错误。

尽管 fix 的天真 Haskell 定义并未终止于 Javascript:

> fix = (f) => f(fix(f))
> factf = (f) => (n) => (n === 0) ? 1 : n * f(n - 1)
> fact = fix(factf) // stack overflow

您必须使用 eta 扩展定义以防止 fix(f):

的循环计算

> fix = (f) => (a) => f(fix(f), a)
> factf = (f, a) => (a == 0) ? 1 : a * f(a - 1)
> fact = fix(factf)
> fact(10) // prints 3628800

Answer 2

事实证明，您尝试实现 U 组合子，不是定点组合子。

而定点Y组合器<b>_Y</b> g = g (_Y g)使我们能够写

 _Y (\r x -> if x==0 then 1 else x * r (x-1)) 5     -- _Y g => r = _Y g
 -- 120

with <b>_U</b> g = g (g) 我们必须写成

 _U (\f x -> if x==0 then 1 else x * f f (x-1)) 5   
                                            -- _U g => f = g, f f == _U g

如您所见，此 _U 在 Haskell 中没有类型。一方面g是函数，g :: a -> b；另一方面，它接收自己作为第一个参数，因此它要求 a ~ a -> b 用于 any 类型 a 和 b。

立即用a -> b替换a -> b中的a会导致无限递归（参见"occurs check"），因为(a -> b) -> b 仍然有 a 需要替换为 a -> b；无穷无尽。

一个解决方案可能是引入递归类型，将 a ~ a -> b 变成 R = R -> b 即

 newtype U b = U {app :: U b -> b}      -- app :: U b -> U b -> b

所以我们可以定义

 _U :: (U b -> b) -> b
 _U g = g (U g)                         -- g :: U b -> b 
   -- = app (U g) (U g)
   -- = join app (U g)
   -- = (join app . U) g                -- (**)

现在有一个类型；并将其用作

 _U (\f x -> if x==0 then 1 else x * app f f (x-1)) 5
                                        -- _U g  =>  f = U g, 
 -- 120                                 -- app f f = g (U g) == _U g

edit: 如果你想实现 Y 组合器作为非递归定义，那么

 _U (\f x -> if x==0 then 1 else x * (app f f) (x-1))
=                                    -------.-               -- abstraction
 _U (\f -> (\r x -> if x==0 then 1 else x * r (x-1)) (app f f))
=          -------.---------------------------------         -- abstraction
 (\g -> _U (\f -> g (app f f))) (\r x -> if x==0 then 1 else x * r (x-1))
=                                                            --  r = app f f 
 _Yn                            (\r x -> if x==0 then 1 else x * r (x-1))

所以

 _Yn :: (b -> b) -> b
 _Yn g = _U (\f -> g (app f f))         -- Y, non-recursively

做这份工作：

 _Yn (\r x -> if x==0 then 1 else x * r (x-1)) 5
 -- 120

(稍后更新：) 或者，更简单，

 _Yn g = _U (\f -> g (app f f))
       = _U (\f -> g (join app f))
       = _U (\f -> (g . join app) f)
       = _U (g . join app)
       = _U ( (. join app) g )

因此

 _Yn :: (b -> b) -> b
 _Yn = _U . (. join app)                -- and, using (**)
     = join app . U . (. join app)

fix 只能用非严格评估的语言输入吗？

Can fix only be typed in non-strict evaluated languages?

haskell

recursion

typechecking

unification

fixpoint-combinators