相关疑难解决方法(0)

我在一个Scheme类中,我很好奇在不使用define的情况下编写递归函数.当然,主要的问题是,如果没有名称,你就无法调用自身内部的函数.

我确实找到了这个例子:它是一个只使用lambda的阶乘生成器.

((lambda (x) (x x))
 (lambda (fact-gen)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((fact-gen fact-gen) (sub1 n)))))))

但我甚至无法理解第一次调用,(lambda(x)(xx)):究竟是做什么的？你在哪里输入你想要得到的阶乘值？

这不是为了上课,这只是出于好奇.

看一下GHC源代码,我可以看到修复的定义是:

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

在一个示例中,修复程序使用如下:

fix (\f x -> let x' = x+1 in x:f x')

这基本上产生了一个数字序列,它们增加1到无穷大.为了实现这一点,修复必须将它接收的函数作为它的第一个参数直接回到该函数.我不清楚上面列出的修复定义是如何做到的.

这个定义是我如何理解修复的工作原理:

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

所以现在我有两个问题:

1. 如何X真的来临意味着修复X中的第一个定义？
2. 在第二个定义中使用第一个定义是否有任何优势？

我很难理解evens-only*&co第145页的The Little Schemer的例子.

这是代码:

(define evens-only*&co
 (lambda (l col)
   (cond
    ((null? l)
     (col '() 1 0))
    ((atom? (car l))
     (cond
      ((even? (car l))
       (evens-only*&co (cdr l)
                    (lambda (newl product sum)
                      (col (cons (car l) newl)
                           (opx (car l) product)
                           sum))))
      (else
       (evens-only*&co (cdr l)
                    (lambda (newl product sum)
                      (col newl product (op+ (car l) sum)))))))
    (else
     (evens-only*&co (car l)
                  (lambda (newl product sum)
                    (evens-only*&co (cdr l)
                                    (lambda (dnewl dproduct dsum)
                                      (col (cons newl dnewl)
                                           (opx product dproduct)
                                           (op+ …

我一直在研究禁止使用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))))))

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

;; 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 的公式。我如何记住它，并在使用它很久之后重现它？

我对计划函数式编程真的很陌生。我最近在 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)))组合器函数的结构不匹配。如何以完全相同的方式在方案中实现它？

(define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter(improve guess x)
                  x)))

(define (improve guess x)
  (average guess(/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.0001))

(define (square x)
  (* x x))

(define (sqrt-g x)
  (sqrt-iter 1.0 x))

这是sqrt的一个程序.问题是当你尝试使用new-if替换if-if时会发生什么.

(define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter(improve guess x)
                  x)))

这是新的,如果

 (define (new-if predicate then-clause else-clause)
      (cond (predicate then-clause)
            (else else-clause)))

我的观点是两个程序的结果是一样的.因为new-if和if可以产生相同的结果.

然而,新的 …

小计划器在第165页上给出了以下内容,因为函数长度为₀.但这是如何工作的？看起来长度lambda被传递给mk-length lambda,它估计长度为lambda,长度为lambda本身作为参数传递.那么,当(length (cdr l))评估底部时,length只是λ本身的长度.但长度lambda有两个参数curry:length和l.那么怎么(length (cdr l))才有意义呢？

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

这是代码(也在这里):

#lang racket
(define poorY
  ((lambda length
    (lambda (ls)
      (cond
        [(null? ls) 0]
        [else (add1 ((length length) (cdr ls)))])))
  (lambda length
    (lambda (ls)
      (cond
        [(null? ls) 0]
        [else (add1 ((length length) (cdr ls)))])))))

当我运行它:

> (poorY '(9 7 8))
. . application: not a procedure;
 expected a procedure that can be applied to arguments
  given: '(#<procedure>)
  arguments...:
   '(#<procedure>)

屏幕截图如下所示:

我正在使用DrRacket作为代表.代码有什么问题？