标签: y-combinator

常规函数可以在其定义中包含对自身的调用,没问题.我无法弄清楚如何使用lambda函数来做这件事,原因很简单,因为lambda函数没有可以引用的名称.有办法吗？怎么样？

任何人都对"组合器"(Y-combinators等而不是 公司)有很好的解释？

我正在寻找一个了解递归和高阶函数的实用程序员,但没有强大的理论或数学背景.

(注意:我正在谈论这些事情)

在几乎所有的例子中,ML类型语言中的y-combinator都是这样编写的:

let rec y f x = f (y f) x
let factorial = y (fun f -> function 0 -> 1 | n -> n * f(n - 1))

这可以按预期工作,但使用时定义y组合器感觉就像是作弊let rec ....

我想使用标准定义在不使用递归的情况下定义此组合器:

Y = ?f·(?x·f (x x)) (?x·f (x x))

直接翻译如下:

let y = fun f -> (fun x -> f (x x)) (fun x -> f (x x));;

然而,F#抱怨它无法弄清楚类型:

  let y = fun f -> (fun x -> f (x x)) (fun x -> f …

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

看起来它会有一个无限递归的类型.

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

或者其他的东西.甚至是一个简单的因子因素

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

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

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

(Y组合器看起来像这样

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

在计划中)或者,更简洁

(? (f) ((? (x) …

我最近一直在阅读关于函数式编程的一些内容,我正试图找到Y-Combinator.我知道您可以使用Y-Combinator以不直接支持递归的语言有效地实现递归.但是,我可能使用的每种语言都支持递归,所以我不确定使用Y-Combinator是多么有用.

是否有一个更好的Y-Combinator使用实例,我错过了？有没有人真正在实际生产代码中使用过一个？或者使用Y-Combinator真的只是一个令人费解的学术练习(尽管很酷).

因此,我花了很多时间阅读并重新阅读The Little Schemer中第9章的结尾,其中应用Y组合器是为该length功能开发的.我认为我的困惑归结为一个单独的声明,对比两个版本的长度(在组合器被分解之前):

A:
  ((lambda (mk-length)
     (mk-length mk-length))
   (lambda (mk-length)
     (lambda (l)
       (cond
         ((null? l) 0 )
         (else (add1
                ((mk-length mk-length)
                 (cdr l))))))))

B:
((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      ((lambda (length)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))
       (mk-length mk-length))))

第170页(第4版)指出A.

当我们将它应用于参数时返回一个函数

而B

不返回功能

从而产生自我应用的无限回归.我很难过.如果B受到这个问题的困扰,我不知道A如何避免它.

我试图弄清楚如何在一行中编写递归函数(例如阶乘,尽管我的函数要复杂得多).为此,我想到了使用Lambda Calculus的 Y组合器.

这是第一个定义:

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

这是减少的定义:

Y g = g(Y g)

我尝试用C#编写它们:

// Original
Lambda Y = f => (new Lambda(x => f(x(x)))(new Lambda(x => f(x(x)))));
// Reduced
Lambda Y = null; Y = g => g(Y(g));

(Lambda是一个Func<dynamic, dynamic>.我首先尝试用它来键入它using,但这不起作用,所以现在它定义了delegate dynamic Lambda(dynamic arg);)

我的阶乘lambda看起来像这样(改编自这里):

Lambda factorial = f => new Lambda(n =>  n == 1 ? 1 : n * f(n - 1)); …

为什么这个函数的类型(a - > a) - > a？

Prelude> let y f = f (y f)
Prelude> :t y
y :: (t -> t) -> t

它不应该是无限/递归类型吗？我打算尝试将我认为类型应该是的,但我出于某种原因无法做到这一点.

y :: (t -> t) -> ?WTFIsGoingOnOnTheRHS?

我不知道f(yf)如何解析为一个值.以下对我来说更有意义:

Prelude> let y f x = f (y f) x
Prelude> :t y
y :: ((a -> b) -> a -> b) -> a -> b

但它仍然令人难以置信的混乱.这是怎么回事？

有没有办法通过高阶函数"包装"递归函数,以便递归调用也被包装？(例如,在每次调用时记录函数的参数.)

例如,假设我们有一个函数,sum()它通过将头部添加到尾部的总和来返回数字列表的总和:

function sum(a) {
    if (a.length === 0) {
        return 0;
    } else {
        return a[0] + sum(a.slice(1));
    }
}

有没有办法编写一个高阶函数,logging()它将sum()函数作为输入,并返回一个函数,sum()在每次递归调用时输出参数？

以下不起作用:

function logging(fn) {
    return function(a) {
        console.log(a);
        return fn(a);
    }
}

sum2 = logging(sum);
sum2([1, 2, 3]);

实际产量:

[1, 2, 3]
-> 6

预期产量:

[1, 2, 3]
[2, 3]
[3]
[]
-> 6

这是否sum()可以重写,以便它可以与Y Combinator风格的"递归"一起使用？

function sum_core(g) {
    return function (a) {
        if (a.length === 0) { …

关于归纳数据类型和模式匹配的 Agda手册:

为确保正常化,归纳事件必须出现在严格的正位置.例如,不允许以下数据类型:

data Bad : Set where
  bad : (Bad ? Bad) ? Bad

Run Code Online (Sandbox Code Playgroud)

因为构造函数的参数中存在负面的Bad.

为什么归纳数据类型需要此要求？