новообращенный впустили в лямбда в схеме

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

и я пытаюсь преобразовать пусть, это то, что я пробовал:

(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? Ну, если вы назначили, что через позволение, у вас есть символ отсылая к нему:

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

Но вы не можете уйти с определением символа для рекурсивного FUNC Тион *.

Относительно того, почему ваш пример не работает, она работает прекрасно, за исключением того, что она создает функцию, взяв в качестве аргумента функцию (который я назвал cont выше) и применяя логику , учитывая, что функция loop. Поскольку у вас тогда нет «цикла», чтобы передать его (так как вы его не связали), он возвращает эту функцию и ничего не предпринимает (кроме того, в ваших возвращенных lambda, low и high не определены).

* Это не совсем так, как вы могли сделать это с помощью 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)) 

Какая работа, как и ожидалось (благодаря слоям Ла mbdas):

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

, но беда в том, что s тело lambda»не может ссылаться на имя loop еще, , как это быть определена (вам мог бы просто заменить letletrec, а затем он сработает, но это не то, о чем вы просите здесь).

Название loop определяется с помощью let является не в рамках внутри выражения инициализации для него. То есть значение let является нерекурсивным. Его рекурсивный вариант, letrec, содержит определение имени, которое должно быть в области внутри инициализационного выражения (просто его значение не может быть запрошено при вычислении значения инициализации).

Там простой трюк, хотя (своего рода бедного человека Y combinator), который эмулирует истинное самореференцию через репликации, что достигается за счет самоприменения, как в

(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, упоминаемое внутри тела лямбда, теперь является только параметром лямбда, таким образом в области.

И поскольку 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)))))))