Haskell 中的 Y Combinator [英] Y Combinator in Haskell

问题描述

是否可以编写Y Combinator 在 Haskell 中?

Is it possible to write the Y Combinator in Haskell?

它似乎具有无限递归类型.

It seems like it would have an infinitely recursive type.

 Y :: f -> b -> c
 where f :: (f -> b -> c)

什么的.即使是一个简单的微因式阶乘

or something. Even a simple slightly factored factorial

factMaker _ 0 = 1
factMaker fn n = n * ((fn fn) (n -1)

{- to be called as
(factMaker factMaker) 5
-}

因发生检查:无法构造无限类型:t = t ->"而失败t2->t1"

fails with "Occurs check: cannot construct the infinite type: t = t -> t2 -> t1"

(Y 组合子看起来像这样

(The Y combinator looks like this

(define Y
    (lambda (X)
      ((lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))
       (lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg)))))))

在方案中)或者，更简洁地

in scheme) Or, more succinctly as

(λ (f) ((λ (x) (f (λ (a) ((x x) a))))
        (λ (x) (f (λ (a) ((x x) a))))))

申请顺序还有

(λ (f) ((λ (x) (f (x x)))
        (λ (x) (f (x x)))))

对于懒惰的版本，这只是一个 eta 收缩.

Which is just a eta contraction away for the lazy version.

如果您更喜欢简短的变量名称.

If you prefer short variable names.

推荐答案

哦

这个维基页面和这个堆栈溢出答案似乎回答了我的问题.
稍后我会写更多的解释.

this wiki page and This Stack Overflow answer seem to answer my question.
I will write up more of an explanation later.

现在，我发现 Mu 类型的一些有趣之处.考虑 S = Mu Bool.

Now, I've found something interesting about that Mu type. Consider S = Mu Bool.

data S = S (S -> Bool)

如果将 S 视为一个集合，并且将等号视为同构，则方程变为

If one treats S as a set and that equals sign as isomorphism, then the equation becomes

S ⇋ S -> Bool ⇋ Powerset(S)

所以 S 是与它们的幂集同构的集合！但是我们从 Cantor 的对角线论证中知道 Powerset(S) 的基数总是严格大于 S 的基数，因此它们永远不会同构.我认为这就是为什么你现在可以定义一个不动点运算符，即使你不能没有一个.

So S is the set of sets that are isomorphic to their powerset! But we know from Cantor's diagonal argument that the cardinality of Powerset(S) is always strictly greater than the cardinality of S, so they are never isomorphic. I think this is why you can now define a fixed point operator, even though you can't without one.

这篇关于Haskell 中的 Y Combinator的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！