get-first - опытный интриган

Question

Пожалуйста, посмотрите на two-in-a-row*? функция в главе 19.

Мой вопрос о (leave '()) в get-first вспомогательная функция. Обратите внимание, что (waddle l) либо вернется '() или атом, который указывает, что список исчерпан, или атом из списка извлечен.

Без (leave '()) он по-прежнему будет возвращать эти два вида значений, но не будет использовать продолжение leave, Но книга говорит без (leave '()) это плохо, я просто не могу понять, почему.

(define two-in-a-row*
  (letrec ([leave id] ; the identity function 
           [fill id]
           [waddle (lambda (l)
                     (cond [(null? l) '()]
                           [(atom? (car l))
                            (begin 
                              (letcc rest
                                     (set! fill rest)
                                     (leave (car l)))
                              (waddle (cdr l)))]
                           [else
                            (begin
                              (waddle (car l))
                              (waddle (cdr l)))]))]
           [get-first (lambda (l)
                        (letcc here
                               (set! leave here)
                               (waddle l)
                               (leave '()) ; why is this part needed???
                               ))]
           [get-next (lambda (l)
                       (letcc here
                              (set! leave here)
                              (fill 'go)))]
           [T? (lambda (a)
                 (let ([n (get-next 'dummy)])
                   (if (atom? n)
                       (or (eq? a n)
                           (T? n))
                       #f)))])
    (lambda (l)
      (let ([fst (get-first l)])
        (if (atom? fst)
            (T? fst)
            #f)))))

Спасибо большое.

Еще один интересный шаг по этой проблеме.

Answer 1

Так что спасибо за примеры Уилла Несса. Я подошел к еще более простым. Так что же такого плохого в этом? - без (leave '()) в get-first,

Короткий ответ:
Обратите внимание, что из моего кода
я) leave всегда будет воссоздан каждый раз, когда мы звоним get-first или же get-next, Это вернется к любому get-first или же get-next,
II) fill приведет к цепочке в зависимости от предыдущего fillи он всегда вернется к get-first,

пример
Входные данные: '(1)

Итак, начнем с оценки get-first на '(1),
я) установить leave
II) начать (waddle '(1)
iii) с тех пор 1 это атом, так что установите fill быть текущим продолжением. Обратите внимание, если мы используем fillтогда это пойдет делать (waddle (cdr l))затем он вернется кget-first, iv) вернуться к get-first используя leave с возвращаемым значением 1,

Тогда мы идем в Eval (T? 1)который в свою очередь пойдет бежать get-next,
я) установить leave
II) запустить fill
iii) начать (waddle '())
iv) возврат () от waddleзатем вернитесь к get-first,

Заметка
1) Если у нас нет (leave '(), затем get-first вернусь '()тогда two-in-a-row* вернуть #f, Таким образом, мы можем получить тот же ответ, но поведение не то, что мы хотим.
2) Если у нас есть, то обратите внимание, что leave сейчас leave создано get-next, таким образом это собирается передать '() в get-next,
3) При наличии более 1 ввода в списке при создании fill он будет создан на основе предыдущего fillв результате получается цепочка в зависимости от предыдущего fill,

Answer 2

Наименование выглядит прочь. Я использовал "yield" для "отпуска" и "следующий" для "заполнения". Я также должен был определить atom? и переписать letcc как call/cc, чтобы он работал в Racket. Вот полный код:

(define two-in-a-row*
  (letrec ([yield '()] 
           [next '()]
           [atom? (lambda (x) (and (not (null? x))
                                   (not (pair? x))))]
           [waddle (lambda (l)
                     (cond [(null? l) '()]
                           [(atom? (car l))
                            (begin 
                              (call/cc (lambda ( here2 )
                                          (set! next here2)
                                          (yield (car l))))
                              (waddle (cdr l)))]
                           [else
                            (begin (waddle (car l))
                                   (waddle (cdr l)))]))]
           [get-first (lambda (l)
                        (call/cc (lambda ( here1 )
                                    (set! yield here1)
                                    (waddle l)
                                    (yield '()) ; why is this part needed???
                                    )))]
           [get-next (lambda ()
                       (call/cc (lambda ( here3 )
                                   (set! yield here3)
                                   (next 'dummy))))]
           [T? (lambda (a)
                 (let ([n (get-next)])  (display (list "next:" n))
                   (and (atom? n)
                        (or (eq? a n)
                            (T? n)))))])
    (lambda (l)
      (let ([a (get-first l)])
        (and (begin                     (display (list "first:" a))
                    (atom? a))
             (T? a))))))

Мы можем увидеть разницу здесь:

(two-in-a-row* '(((7) (b)) c (d)))
  ; w/out yield () : (first: 7)(next: b)(next: c)(next: d)(first: ())#f
  ; w/    yield () : (first: 7)(next: b)(next: c)(next: d)(next: ())#f
  ; w/    yield #f : (first: 7)(next: b)(next: c)(next: d)(next: #f)(next: #f)#t

(two-in-a-row* '(((7) (b)) c ()))
  ; w/out yield () : (first: 7)(next: b)(next: c)(first: ())#f
  ; w/    yield () : (first: 7)(next: b)(next: c)(next: ())#f
  ; w/    yield #f : (first: 7)(next: b)(next: c)(next: #f)(next: #f)#t

(two-in-a-row* '(((7) (b)) b ()))
  ; w/out yield () : (first: 7)(next: b)(next: b)#t
  ; w/    yield () : (first: 7)(next: b)(next: b)#t
  ; w/    yield #f : (first: 7)(next: b)(next: b)#t

Answer 3

Это сложно. Подсказка в книге - это wow! Ответить. Студент говорит wow! потому что они поняли () возвращается из другой функции.

Это не ясно ни в книге, ни с помощью drracket, и мне потребовалось некоторое время, чтобы понять, но ключ к пониманию:

1. get-first называется waddle сделать fill продолжение.
2. waddle (когда не используются продолжения) возвращается к get-first,

Но

1. get-next звонки fill,
2. fill продолжается в waddle
3. waddle использования leave вернуться в get-next скорее, чем get-first,

Но в случае (waddle '()), waddle не использует leave вернуться в get-next, Возвращается нормально. А это значит, что он возвращается к get-first,

Это означает, что get-next на самом деле не получит () возвращаемое значение Это не получит это значение, потому что waddle возвращается к get-first вместо.

Теперь перейдем к интересной части.

1. Мы знаем, что для ценности (), waddle возвращается к get-first когда мы хотим, чтобы он вернулся get-next,
2. Мы знаем это get-next наборы leave вернуться в get-next,
3. Следовательно, get-first можешь использовать leave вернуться в get-next,

Настоящая причина, по которой это сложно, в том, что вы смотрите на сценарий, когда вы не используете (leave '()) в get-first,

1. fill звонки вразрез с (),
2. waddle возвращается к get-first,
3. get-first затем возвращается (),

И это эквивалентно:

  (let ([fst '()])     ;; was (let ([fst (get-first l)])
    (if (atom? fst)
        (T? fst)
        #f)))))

Который возвращает то же значение, что и версия, которая возвращается в get-next:

       [T? (lambda (a)
             (let ([n '()])      ;; was (let ([n (get-next 'dummy)])
               (if (atom? n)
                   (or (eq? a n)
                       (T? n))
                   #f)))])

Оба #f, но только случайно! Никто не говорил, что книга не заставит вас задуматься;)