1

这是原始形式：

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

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

4

2 回答 2

3

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

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

或者更简洁地使用 a 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))

但是你不能为你的递归函数定义一个符号*。

至于为什么您的示例不起作用，它工作得非常好，除了它创建了一个function ，将一个function（我在上面调用过）作为参数并在给定 functioncont的情况下应用您的逻辑。由于您没有任何“循环”来传递它（因为您没有绑定它），它返回该函数并继续不做任何事情（此外，在您的返回中，并且未定义）。looplambdalowhigh

* 这并不完全正确，因为您可以在 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))

哪个按预期工作（感谢 lambdas 层）：

(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))
于 2016-02-23T09:48:22.690 回答
1

你可以试试写

(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，然后它会起作用，但这不是你在这里要问的）。

loop定义let的名称不在它的 init 表达式的范围内。这就let是非递归的含义。它的递归变体letrec确实提供了要定义的名称，使其位于 init-expression 的范围内（只是在计算 init-value 时不允许查询其值）。

不过有一个简单的技巧（一种穷人的Y 组合器），它通过复制来模拟真正的自我引用，这是通过自我应用实现的，如

(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的——loop在 lambda 体内引用的名称现在只是一个 lambda 参数，因此在范围内。

由于是普通的、非递归的，因此很容易用一个简单的-applicationlet重写它，如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)))))))
于 2016-02-23T15:07:02.667 回答