标签: y-combinator

我无法理解Y-combinator,所以我尝试实现一个在没有本机实现的情况下启用递归的函数.经过一番思考,我最终得到了这个:

Y = ?x.(?v.(x x) v)

哪个比实际的短:

Y = ?f.(?x.f (x x)) (?x.f (x x))

而且,令我惊讶的是,工作.一些例子:

// JavaScript
Y = function(x){
  return function(v){
    return x(x, v);
  };
};
sum = Y(function(f, n){
  return n == 0 ? 0 : n + f(f, n - 1);
});
sum(4);

; Scheme
(define Y (lambda (x) (lambda (v) (x x v))))
(define sum (Y 
    (lambda (f n) 
        (if (equal? n 0) 
            0 
            (+ n (f f (- n 1)))))))
(sum 4)

两个片段按预期输出10(从0到4的总和).

这是什么,为什么它更短,为什么我们更喜欢更长的版本？

我的大脑似乎是在自虐模式,所以在之后被淹死这个,这个和这个,它想勾搭C#一些DIY.

我想出了下面,我不认为是Y组合子,但它确实似乎设法使非递归函数的递归,没有提及自己:

Func<Func<dynamic, dynamic>, Func<dynamic, dynamic>> Y = x => x(x);

所以给出这些:

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(self)(n - 1);
Func<dynamic, Func<dynamic, dynamic>> fib = 
                  self => n => n < 2 ? n : self(self)(n-1) + self(self)(n-2);

我们可以生成这些:

Func<dynamic, dynamic> Fact = Y(fact);
Func<dynamic, dynamic> Fib = Y(fib);

Enumerable.Range(0, 10)
          .ToList()
          .ForEach(i => Console.WriteLine("Fact({0})={1}", i, Fact(i)));

Enumerable.Range(0, …

是否有一个固定点组合器用于创建相互递归函数的元组？即我正在寻找像Y-Combinator这样的东西,但它需要多个"递归"*函数,并将返回一个函数元组？

*:当然不是真正的递归,因为它们是以通常的Y-Combinator方式将自己(和兄弟姐妹)作为参数编写的.

我对使用定点组合器的实际例子很感兴趣(例如C++中的y-combinator.你有没有使用带有egg的固定点组合器或绑定真实的实时代码？

我在蛋中发现这个例子有点密集:

void egg_example()
{
    using bll::_1;
    using bll::_2;

    int r =
        fix2(
            bll::ret<int>(
                // \(f,a) -> a == 0 ? 1 : a * f(a-1)
                bll::if_then_else_return( _2 == 0,
                    1,
                    _2 * lazy(_1)(_2 - 1)
                )
            )
        ) (5);

    BOOST_CHECK(r == 5*4*3*2*1);
}

你能解释一下这一切是怎么回事吗？

是否有一个很好的简单例子,或许使用bind可能比这个更少的依赖？

我有一个函数,它根据迭代计算一个固定点:

equivalenceClosure :: (Ord a) => Relation a -> Relation a
equivalenceClosure = fst . List.head                -- "guaranteed" to exist 
                   . List.dropWhile (uncurry (/=))  -- removes pairs that are not equal
                   . U.List.pairwise (,)            -- applies (,) to adjacent list elements
                   . iterate ( reflexivity
                             . symmetry
                             . transitivity
                             )

请注意,我们可以从这里抽象到:

findFixedPoint :: (a -> a) -> a -> a
findFixedPoint f = fst . List.head
                 . List.dropWhile (uncurry (/=))  -- dropWhile we have not reached the fixed point
                 . …

我最近在Y组合器周围花了一些时间,我发现它通常定义(或多或少)如下(这是在C#中,但选择的语言并不重要):

public delegate TResult SelfApplicable<TResult>(SelfApplicable<TResult> r);

public static TResult U<TResult>(SelfApplicable<TResult> r)
{
    return r(r);
}

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f)
{
    return U<Func<TArg1, TReturn>>(r => arg1 => f(U(r))(arg1));
}

虽然这是完美的功能(双关语),但似乎我的定义更简单:

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f)
{
    return f(n => Y(f)(n));
}

有没有理由说后一个定义不常见(我还没有在网上找到它)？它可能与定义Y本身有关吗？

我相信我的理解数学的Y组合子的想法:它返回的功能给出一个固定点F,从而f = Y(F)在那里f满足f == F(f).

但我不明白实际的计算程序是如何明智的？

我们来看一下这里给出的javascript示例:

var Y = (F) => ( x => F( y => x(x)(y) ) )( x => F( y => x(x)(y) ) )
var Factorial = (factorial) => (n => n == 0 ? 1 : n * factorial(n-1))

Y(Factorial)(6) == 720    // => true
computed_factorial = Y(Factorial)

我不明白的部分是如何computed_factorial实际计算函数(固定点)？通过跟踪Y的定义,你会发现它在该部分遇到无限递归x(x),我看不到那里隐含的任何终止案例.然而,奇怪的确回来了.谁能解释一下？

我试图解决最大子序列和问题,并提出了一个neato解决方案

msss :: (Ord a, Num a) => [a] -> a
msss = f 0 0

f gmax _ [] = gmax
f gmax lmax (x:xs) = 
  let g = max (lmax + x)
  in  f (g gmax) (g 0) xs

您调用包装函数msss,然后调用f该函数,然后实际执行该工作.解决方案很好,afaik工作正常.如果由于某种原因我必须解决生产代码中的最大子序列和问题,那就是我会这样做的.

然而,包装函数确实让我感到困惑.我喜欢它如何在haskell中,如果你足够坚持,你可以将你的整个程序写在一条线上,真正让家庭认为程序几乎只是一个大表达.所以我想我会尝试消除额外挑战的包装函数.

现在我遇到了经典问题:如何进行匿名递归？当你不能给函数命名时,你如何做递归？值得庆幸的是,计算机的父亲在很久以前通过发现定点组合器来解决这个问题,其中最受欢迎的是Y Combinator.

我已经做了各种尝试来设置Y组合器,但它们无法通过编译器.

msss' :: [Int] -> Int
msss' = (\y f x -> f (y y f) x) 
        (\y f x -> f (y y f) …

我正在尝试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操作？我想我将不得不应用组合器,以允许递归,但我无法弄清楚如何做到这一点.

参考: …

这是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 => …