我正在尝试stack使用定点组合器在lambda演算中定义数据结构.我试图定义两个操作,insertion以及removal元素,所以,push和pop,但是我能够定义的唯一一个,插入,不能正常工作.删除我无法弄清楚如何定义.

这是我对push操作的方法,我的定义是stack:

Stack definition:
STACK = \y.\x.(x y)
PUSH = \s.\e.(s e)

我的堆栈初始化为一个元素来指示底部; 我在0这里使用:

stack = STACK 0 = \y.\x.(x y) 0 = \x.(x 0)       // Initialization
stack = PUSH stack 1 = \s.\e.(s e) stack 1 =     // Insertion
    = \e.(stack e) 1 = stack 1 = \x.(x 0) 1 =
    = (1 0)

但是现在,当我尝试插入另一个元素时,它不起作用,因为我的初始结构已被解构.

如何修复STACK定义或PUSH定义,以及如何定义POP操作？我想我将不得不应用组合器,以允许递归,但我无法弄清楚如何做到这一点.

参考: …

我希望你们都没事.我正在海港实施定点Y-combinator,我遇到了一些麻烦.嗯,Y-组合子可以由lambda演算定义为:

Y = (?h.?F.F(? x.((h(h))(F))(x))) (?h.?F.F(? x.((h(h))(F))(x)))

我正试图通过性能问题对Y-combinator应用memoization.我目前的实施是:

Function YMem( bF, aCache )
   Local xAnswer
    If !lCache ; lCache := { } ; EndIf
    Return { |Arg| Iif( aCache[ Arg ] ;
        , /* then      */ aCache[ Arg ];
        , /* otherwise */ aCache[ Arg ] := ;
            Eval( Eval( bF, { |N| Eval( Eval( YMem, bF, aCache ), N ) } ), Arg ) ) }

基本上,我不能在块内使用语句,但我可以使用表达式,它工作得很好.我正在避免无限递归,并且限制通过0到无限.

直到这个时候,它编译得很好,但是当我试图访问外部块的变量时,Harbour在Face中踢我!

为了测试的Y组合子的实现,我尝试应用斐波那契序列的简单implemetation,但是当我返回接收参数的块G,隐式返回接收参数的块N,Gbecames对我来说不可用,编译器说我说"外部代码块变量是遥不可及的". …

这是Scala中Y-combinator的一个实现:

scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)
Y: [T](func: (T => T) => (T => T))T => T

scala> def fact = Y {
     |           f: (Int => Int) =>
     |             n: Int =>
     |               if(n <= 0) 1
     |               else n * f(n - 1)}
fact: Int => Int

scala> println(fact(5))
120

Q1:结果120是如何逐步产生的？因为Y(func)定义为func(Y(func)),Y应该变得越来越多,Y在哪里迷失120了？在形式过程中如何出现？

Q2:有什么区别

def Y[T](func: (T => T) => (T => …

这是Haskell中定点组合器的通常定义:

fix :: (a -> a) -> a
fix f = let x = f x in x

在https://wiki.haskell.org/Prime_numbers上,他们定义了一个不同的定点组合子:

_Y   :: (t -> t) -> t
_Y g = g (_Y g)                -- multistage, non-sharing,  g (g (g (g ...)))
    -- g (let x = g x in x)    -- two g stages, sharing

_Y是一个非共享的固定点组合器,在这里安排递归"伸缩"多级素数生产(生产者塔).

这到底是什么意思？在这种情况下,"共享"与"非共享"是什么？有_Y什么不同fix？

我很困惑.我想生成一个例子(在Clojure中),演示如何使用定点组合器来评估在无限数量的应用之后在数学上收敛的序列的固定点,但事实上,在有限数量的步骤之后收敛有限的浮点精度.我显然在这里遗漏了一些东西.

(defn Y [r]
  ((fn [f] (f f))
   (fn [f]
     (r (fn [x] ((f f) x))))))

(defn simple-convergent [func]
  (fn [x]
    (if (zero? x)
      0.0
      (* 0.5 (func x)))))

我可以得到

user=> ((Y simple-convergent) 0.)
0.0
user=> ((Y simple-convergent) 0.2)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

我不明白这个堆栈溢出.更一般地说,与我之前的帖子有关,我想知道是否有人可以呈现定点组合器的"正确"版本,其可以用于以这种方式近似序列的固定点.

我正在摆弄JavaScript中的Cominators,当我偶然发现维基百科说:"Y组合子可以在SKI演算中表达为:Y = S(K(SII))时,我很自豪(希望)让S上班." S(S(KS)K)(K(SII)))",所以我必须尝试:

var I = function (x) {
            return x;
        };

var K = function (x) {
        return function(){
            return x;}
        };

var S = function (x) {
           return function (y) {
               return function (z) {
                   return x(z)(y(z));
               }
           }
       };

var Y = S (K(S(I)(I))) (S(S(K(S))(K)) (K(S(I)(I))));

Y;    //evals to:
//function (z) {return x(z)(y(z));}

//And this (lifted from Crockford's Site):
var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : …

我一直在研究禁止使用def-before-def并且没有可变单元格(no set!或setq)的语言如何提供递归.我当然跑过(着名的？臭名昭着的？)Y组合者和朋友,例如:

• http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
• http://okmij.org/ftp/Computation/fixed-point-combinators.html
• http://www.angelfire.com/tx4/cus/combinator/birds.html
• http://en.wikipedia.org/wiki/Fixed-point_combinator

当我以这种方式实现"letrec"语义时(也就是说,允许定义一个局部变量使得它可以是一个递归函数,在封面下它不会引用它自己的名字),组合器我最后写的看起来像这样:

Y_letrec = ?f . (?x.x x) (?s . (?a . (f ((?x.x x) s)) a))

或者,将U组合子分解出来:

U = ?x.x x
Y_letrec = ?f . U (?s . (?a . (f (U s)) a))

读这个:Y_letrec是一个带有待递归函数的函数f. f必须是一个单参数函数,它接受s,可以调用实现自递归s的函数f.f期望定义并返回执行"实际"操作的"内部"函数.该内部函数接受参数a(或者在一般情况下接受参数列表,但不能用传统的表示法表示).调用Y_letrec的结果是调用的结果 f,并且它被假定为"内部"函数,准备被调用.

我这样设置的原因是我可以直接使用待递归函数的解析树形式,而无需修改,只是在处理letrec时转换期间在其周围包裹一个额外的函数层.例如,如果原始代码是:

(letrec ((foo (lambda (a) (foo (cdr a))))))

然后转换后的形式将是:

(define foo (Y_letrec (lambda (foo) (lambda (a) (foo (cdr a))))))

请注意,内部函数体在两者之间是相同的. …

Y - Combinator

我一直在努力学习Y - Combinators (对它的解释也很可爱)并且从这个wiki中得到了一个例子.无论是Haskell还是Python,都会对这个主题进行深入的解释.Pleaaase!

码

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

问题

应用时调用的函数fix返回,我不知道为什么; 当我按照堆栈进行可视化时.9fix(\x -> 9)f(f ... (fix f) ...)

>> fix (\x -> 9)
>> 9

我知道我可以像这样在SML中编写y-combinator:首先声明一个新的数据类型以绕过由于循环引起的类型不匹配.

datatype 'a mu = Roll of ('a mu -> 'a)
val unroll = fn Roll x => x

现在您可以轻松定义y-combinator:

val Y = fn f => (fn x => fn a => f (unroll x x) a)
          (Roll (fn x => fn a => f (unroll x x) a)))

然后你就完成了,你可以像这样使用它:

val f = Y (fn f => fn n => if n = 0 then 1 else n * f (n-1))

我的问题是:是否有其他方法在SML中实现y-combinator？

;; compute the max of a list of integers

(define Y
  (lambda (w)
    ((lambda (f)
       (f f))
     (lambda (f)
       (w (lambda (x)
            ((f f) x)))))))

((Y
  (lambda (max)
    (lambda (l)
      (cond ((null? l) -1)
            ((> (car l) (max (cdr l))) (car l))
            (else (max (cdr l)))))))
 '(1 2 3 4 5))

我想了解这个结构。有人能给这段代码一个清晰简单的解释吗？

例如，假设我忘记了 Y 的公式。我如何记住它，并在使用它很久之后重现它？