lambda - 在方案中将 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)))))

您绝对可以在函数中直接使用它，定义“内部”递归部分，但这不能使用简单的 lambda 而不使用 let 来实现:该函数需要引用自身(因为它是递归的)，并且您只能通过为其分配一个名称来做到这一点。 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 上面)并应用您的逻辑给定该函数循环。由于您没有任何“循环”来传递它(因为您没有绑定(bind)它)，因此它返回该函数并继续执行任何操作(此外，在返回的 lambda 中，low 和 high 未定义)。

* 这并不完全正确，因为您可以使用 combinators 来做到这一点在你的 lambda 上，但这会使其比应有的复杂得多:

(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))