在方案中将 let 转换为 lambda

Question

这是原来的形式：

(define (split-by l p k)
  (let loop ((low '())
             (high '())
             (l l))
    (cond ((null? l)
           (k low high))
          ((p (car l))
           (loop low (cons (car l) high) (cdr l)))
          (else
           (loop (cons (car l) low) high (cdr l))))))

我正在尝试转换 let，这是我尝试过的：

(define (split-by l p k)
  (lambda (loop)     
    (cond ((null? l) (k low high))
          ((p (car l)) 
           (loop low (cons (car l) high) (cdr l)))
          (else
           (loop (cons (car l) low) high (cdr l))
           ((low '()) (high '()) (l l))))))

我不知道如何解决这个问题，所以如果有人能帮助我解决我做错的事情，那将是一个很大的帮助。

Answer 1

如果我理解正确你在做什么，p 是一个谓词，你根据这个拆分列表 l，用聚合函数聚合你的两个结果列表 k;在伪代码中：

(split-by l p k) => (k {x in l | !p(x)} {x in l | p(x)})

替换 let 时出现的问题是 loop 函数是递归定义的。它的形式是：

(define (loop low high lst)
    (cond
        ((null? lst) <some value>)
        (<some predicate> (loop (cons (car lst) low) high (cdr lst)))
        (else (loop low (cons (car lst) high) (cdr lst)))))

你绝对可以直接在你的函数中使用它，定义 'inner' 递归部分，但这不能使用没有 let 的简单 lambda 来实现：函数需要 引用它自己（因为它是递归的），你只能通过给它一个名字来做到这一点。 define会那样做，let会让你那样做，但不管你怎么转，你都需要那个自我参照。如果你很聪明并继续传递：

(lambda (low high lst cont)
    (cond
        ((null? lst) (agg high lst))
        ((pred? (car lst)) (cont low (cons (car lst) high) (cdr lst) cont))
        (else (cont (cons (car lst) low) high (cdr lst) cont))))

您通过显式删除了自我引用，但是您将什么传递为 cont ？好吧，如果你通过 let 分配它，你有一个引用它的符号：

(define (split-by2 lst pred? agg)
    (let ((f (lambda (low high lst cont)
                (cond
                    ((null? lst) (agg low high))
                    ((pred? (car lst)) (cont low (cons (car lst) high) (cdr lst) cont))
                    (else (cont (cons (car lst) low) high (cdr lst) cont))))))
        (f '() '() lst f)))

或者更简洁地使用 define，它做完全相同的事情（不需要继续传递）：

(define (split-by3 lst pred? agg)
    (define (f low high lst)
        (cond
            ((null? lst) (agg low high))
            ((pred? (car lst)) (f low (cons (car lst) high) (cdr lst)))
            (else (f (cons (car lst) low) high (cdr lst)))))
    (f '() '() lst))

它们的操作都相似：

(split-by '(1 2 3 4) (lambda (x) (> x 2)) list)
=> ((2 1) (4 3))   
(split-by2 '(1 2 3 4) (lambda (x) (> x 2)) list)
=> ((2 1) (4 3))   
(split-by3 '(1 2 3 4) (lambda (x) (> x 2)) list)
=> ((2 1) (4 3))

但是您无法为递归函数定义一个符号*。

至于为什么你的例子不起作用，它工作得很好，除了它创建了一个函数，作为参数一个函数（我在上面称之为 cont）并应用你的逻辑 给定函数 loop。因为你没有任何 'loop' 来传递它（因为你没有绑定它），所以它 returns 起作用并继续不做任何事情（此外，在你返回的 lambda, low 和 high 未定义）。

* 这并不完全正确，因为您可以在您的 lambda 上使用 combinators 来做到这一点，但这会使它很多比它应该的更复杂：

(define Y
  (lambda (h)
    ((lambda (x) (x x))
     (lambda (g)
       (h (lambda args (apply (g g) args)))))))

(define (split-ycomb lst pred? agg)
    ((Y 
        (lambda(f)
            (lambda (low high l)
                (cond
                    ((null? l) (agg low high))
                    ((pred? (car l)) (f low (cons (car l) high) (cdr l)))
                    (else (f (cons (car l) low) high (cdr l)))))))
    '() '() lst))

或者更 ~~更丑陋~~ 更纯粹的版本，带有内联组合器：

(define (split-ycomb2 lst pred? agg)
    (((lambda (h)
        ((lambda (x) (x x))
            (lambda (g)
                (h (lambda args (apply (g g) args)))))) 
        (lambda(f)
            (lambda (low high l)
                (cond
                    ((null? l) (agg low high))
                    ((pred? (car l)) (f low (cons (car l) high) (cdr l)))
                    (else (f (cons (car l) low) high (cdr l)))))))
    '() '() lst))

按预期工作（多亏了 lambda 层）：

(split-ycomb '(1 2 3 4) (lambda (x) (> x 2)) list)
=> ((2 1) (4 3))
(split-ycomb2 '(1 2 3 4) (lambda (x) (> x 2)) list)
=> ((2 1) (4 3))

Answer 2

你可以试试写

(define (split-by l p k)  
  (let ((loop 
          (lambda (low high l)
             (cond 
               ((null? l)
                  (k low high))
               ((p (car l))
                  (loop low (cons (car l) high) (cdr l)))
               (else
                  (loop (cons (car l) low) high (cdr l)))))))
    (loop '() '() l)))

但问题是 lambda 的主体还不能引用 loop 名称，因为它正在 定义（你可以将 let 替换为 letrec，然后它就可以工作，但这不是你在这里问的）。

let 定义的名称 loop 不在它的初始化表达式的范围内。这就是 let 非递归的意思。它的递归变体 letrec 确实提供了被定义的名称，在 init-expression 中 in scope （只是它的值不允许在以下情况下被查询）计算初始值）。

虽然有一个简单的技巧（一种穷人的Y combinator），它通过复制模拟真正的自引用，这是通过[=39=实现的]自助申请，如

(define (split-by l p k)  
  (let ((foo 
          (lambda (loop low high l)
             (cond 
               ((null? l)
                  (k low high))
               ((p (car l))
                  (loop loop low (cons (car l) high) (cdr l)))
               (else
                  (loop loop (cons (car l) low) high (cdr l)))))))
    (foo foo '() '() l)))

一切都在阳光下，即非递归 let -- 在 lambda 体内引用的 loop 名称现在只是一个 lambda 参数，因此 范围内.

而且由于 let 是普通的、非递归的，所以很容易用一个简单的 lambda 应用程序重写它，如

(define (split-by l p k)  
  ((lambda (foo) (foo foo '() '() l))   ; (lambda (loop ...
   (lambda (loop low high l)            ;   is duplicated into the two foos
             (cond 
               ((null? l)
                  (k low high))
               ((p (car l))
                  (loop loop low (cons (car l) high) (cdr l)))
               (else
                  (loop loop (cons (car l) low) high (cdr l)))))))

在方案中将 let 转换为 lambda

convert let into lambda in scheme

lambda

scheme

let

named

letrec