标签: y-combinator

为了了解固定点组合器是什么和用于什么,我写了自己的.但不是用严格的匿名函数编写它,比如维基百科的例子,我只使用了define:

(define combine (lambda (functional)
                  (functional (lambda args (apply (combine functional) args))))

我用factorial和fibonacci的函数来测试它,它似乎工作.这是否符合定点组合器的正式定义？

几天前我在"C#匿名递归"中浏览了这个网站.本文的主旨是以下代码在C#中不起作用:

Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

然后,文章详细介绍了如何使用currying和Y-combinator回到C#中的"Anonymous Recursion".这很有趣,但我担心日常编码有点复杂.此时至少......

我喜欢看自己的东西,所以我打开了Mono CSharp REPL并输入了该行.没有错误.所以,我进来了fib(8);.令我非常惊讶的是,它奏效了!REPL回复了21!

我想也许这可能是REPL的一些魔力,所以我点了'vi',输入以下程序,然后编译它.

using System;

public class Program
{
    public static void Main(string[] args)
    {
        int x = int.Parse(args[0]);
        Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
        Console.WriteLine(fib(x));
    }
}

它也完美地建造和运行!

我在Mac上运行Mono 2.10.我现在无法访问Windows计算机,所以我无法在Windows上的.NET上进行测试.

这是在.NET上修复过的还是Mono的静音功能？这篇文章已经有几年了.

如果它只是单声道,我不能等待下一次面试,他们要求我用我选择的语言(Mono …

我有一个递归函数(在C#中),我需要调用大约8亿次; 这显然通常会在大约第900次呼叫后导致堆栈溢出.我已经将它踢出了多个循环,但递归模式更容易,维护更清晰.

我正在考虑使用y-combinator实现递归函数,就像我正在阅读和看到的那样,它应该解决堆栈溢出问题,并修复多个嵌套循环.

有没有人有使用y-combinator的经验？我还会陷入堆栈溢出吗？

以一个阶乘的简单例子为例.大多数数字大于5,000的因子将导致堆栈溢出.如果我在那个场景中正确使用了y-combinator,它会修复堆栈溢出吗？

它实现起来似乎微不足道,所以我想在开发工作/资源实现和学习y-combinator之前确认它.

我正在尝试使用y-combinator在scala中定义gcd:

object Main {
  def y[A,B]( f : (A => B) => A => B ) : A => B = f(y(f))
  def gcd = y[(Int,Int),Int]( (g) => (x,y) => if (x == 0) y else g(y % x, x) )
}

但我收到一个错误:

Main.scala:3: error: type mismatch;                                                  
 found   : (Int, Int) => Int                                                               
 required: (Int, Int) => Int                                                               
    def gcd = y[(Int,Int),Int]( (g) => (x :Int,y :Int) => if (x == 0) y else g(y % x, x) ) 
                                                       ^ …

我是定点组合器世界的新手,我猜他们已经习惯了匿名的lambdas,但我还没有真正使用它们,甚至无法完全绕过它们.

我在Javascript中看到了Y-combinator的例子,但是还没能成功运行它.

这里的问题是,有人可以给出一个直观的答案:

• 什么是定点组合器(不仅在理论上,而且在某些示例的上下文中,揭示该上下文中的定点究竟是什么)？
• 除了Y-combinator之外,还有哪些其他类型的定点组合器？

奖励积分:如果示例不仅仅是一种语言,最好也是在Clojure中.

更新:

我已经能够在Clojure中找到一个简单的例子,但仍然发现很难理解Y-Combinator本身:

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

虽然这个例子很简洁,但我发现很难理解函数中发生了什么.提供的任何帮助都是有用的.

在构建一个基于lambda的小型元编程库时,我有必要在C++ 14泛型lambda中使用递归来实现左折叠.

我自己的解决方案是将lambda本身作为其参数之一传递,如下所示:

template <typename TAcc, typename TF, typename... Ts>
constexpr auto fold_l_impl(TAcc acc, TF f, Ts... xs)
{
    // Folding step.
    auto step([=](auto self)
    {
        return [=](auto y_acc, auto y_x, auto... y_xs)
        {
            // Compute next folding step.
            auto next(f(y_acc, y_x));

            // Recurse if required.
            return static_if(not_empty(y_xs...))
                .then([=]
                    {
                        // Recursive case.
                        return self(self)(next, y_xs...);
                    })
                .else_([=]
                    {
                        // Base case.
                        return next;
                    })();
        };
    });

    // Start the left-fold.
    return step(step)(acc, xs...);
}

step是从递归开始的"主要"lambda.它返回一个具有所需左折签名的函数(累加器,当前项,剩余项......) …

我对计划函数式编程真的很陌生。我最近在 lambda 演算中遇到了 Y-combinator 函数，就像这样Y ? (?y.(?x.y(xx))(?x.y(xx)))。我想在方案中实现它，我搜索了很多，但我没有找到任何与上面给出的结构完全匹配的实现。我发现的其中一些如下：

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

和

(define Y
  (lambda (r)
    ((lambda (f) (f f))
     (lambda (y)
       (r (lambda (x) ((y y) x)))))))

如您所见，它们与此Y ? (?y.(?x.y(xx))(?x.y(xx)))组合器函数的结构不匹配。如何以完全相同的方式在方案中实现它？

我有一个coins = [200; 100; 50; 20; 10; 5; 2; 1] 列表和这个递归函数来计算有多少种方法可以提供一定量的变化（Project Euler 问题 31 的剧透警报）：

let rec f acc coins amount =
    if amount < 0 then 0L
    elif amount = 0 then acc
    else
        match coins with
        | [] -> 0L
        | c::cs ->
            f (acc + 1L) coins (amount - c) + f acc cs amount

除了 aStackOverflowException对于大值之外，该函数需要很长时间。所以我想起了Y 组合器，并很好奇如何将它应用于这个问题。在一点帮助和对函数签名的两个小改动后，我得到了这个：

let f f acc coins amount =
    if amount < …

我想在薄荷细节中理解我们如何设法从Y-combinator的lambda演算中获得:

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

到以下实现(在Scala中):

def Y[A, B](f: (A => B) => A => B): A => B = (x: A) => f(Y(f))(x)

我对函数式编程很陌生,但我对lambda演算以及替换过程的工作方式有了不错的理解.然而,我很难理解我们是如何从正式表达式实现的.

此外,我想知道如何告诉我的函数的参数的类型和数量以及它的返回类型是什么lambda？

我正在做一些类似 y 组合器的 lambda 包装的实验（尽管我知道它们实际上并不是严格意义上的 y 组合器），但我遇到了一个非常奇怪的问题。我的代码在调试配置中完全按照我的预期运行（关闭优化），但跳过了发布中的大（而且很重要！）位（设置为Optimizations (Favor Speed) (/Ox)）。

请注意，lambda 函数的内部基本上无关紧要，它们只是为了确保它可以正确递归等。

// main.cpp
#include <iostream>
#include <string>
#define uint unsigned int

// Defines a y-combinator-style thing to do recursive things. Includes a system where the lambda can declare itself to be obsolete.
// Yes, it's hacky and ugly. Don't worry about it, this is all just testing functionality.
template <class F>
class YCombinator {
public:
    F m_f; // the lambda will be stored here
    bool m_selfDestructing = …