Блог

Я выполняю упражнение, чтобы захватить «листья» вложенного списка в схеме (из SICP). Вот упражнение ввод-вывод:

 (define x (list (lis 1 2) (list 3 4)))
(fringe x)
; (1 2 3 4)

(fringe (list x x))
; (1 2 3 4 1 2 3 4)
 

Теперь я придумал два ответа на этот вопрос: один рекурсивный и один итеративный. Вот мои две реализации ниже:

 (define (fr lst)
  (cond ((null? lst) '())
        ((not (pair? (car lst))) (cons (car lst) (fr (cdr lst))))
        (else (append (fr (car lst)) (fr (cdr lst))))))
 

 (define (add-element-to-list lst elem)
  (if (null? lst)
      (list elem)
      (cons (car lst) (add-element-to-list (cdr lst) elem))))

(define (fringe lst)
 (define L '())
  (define (iter lst)
    (if (not (pair? (car lst)))
        (set! L (add-element-to-list L (car lst))) ; update the list if it's a leaf
        (iter (car lst)))                          ; otherwise recurse
    (if (not (null? (cdr lst))) (iter (cdr lst)))  ; and if we have a cdr, recurse on that
    L
    )
  (iter lst)
)
 

 (fringe x)
(fr x)
(fr (list x x))
(fringe (list x x))
; (1 2 3 4)
; (1 2 3 4)
; (1 2 3 4 1 2 3 4)
; (1 2 3 4 1 2 3 4)
; OK
 

Проблема для меня в том, что это упражнение заняло у меня целую вечность, чтобы разобраться с тонной ударов по голове на этом пути (и мне все еще трудно «понять», когда я пишу это). Вот несколько вещей, с которыми я боролся, и посмотрим, есть ли какие-либо предложения о способах решения этих проблем в схеме:

1. Сначала я думал, что есть два случая. Обычный/скалярный случай и вложенный случай. Однако, похоже, что на самом деле их три! Есть обычный случай, вложенный случай, а затем нулевой случай-и во внутренних списках также есть нулевой случай! Есть ли хороший общий шаблон или что-то, что объясняет нулевой случай? Это то, о чем часто говорят?
2. В итеративном случае, почему я должен возвращаться L в конце? Почему (iter lst) бы просто не вернуть это (т. Е., если я удалил автономный — L в нижней части iter функции).
3. Наконец, существует ли «более чистый» способ реализации итеративного случая? Похоже, у меня так много кода, где его, вероятно, можно было бы улучшить.

Причина, по которой существует три случая, заключается в том, что вы импортируете некоторое скалярное / векторное различие из какого-либо другого языка: в схеме его нет, и это бесполезно. Вместо этого список-это рекурсивно определенный объект: список-это либо пустой список, либо пара чего-то и список. Это означает, что необходимо провести два различия, а не одно: является ли объект парой и является ли объект пустым списком:

 (define (lyst? o)
  (or (null? o)
      (and (pair? o) (lyst? (cdr o)))))
 

Это совершенно отличается от векторного / скалярного различия. Я не знаю, с какого языка вы это получаете, но просто подумайте о том, как будет работать математика: векторы определяются над некоторым скалярным полем, и нет вектора, который также является скаляром. Но для списков есть список, который не является парой. Просто перестаньте думать о векторах и скалярах: это не очень полезный способ думать о списках, парах и пустом списке.

Итеративная версия слишком ужасна, чтобы думать о ней: есть причина, по которой SICP еще не представлен set! .

Во-первых, на самом деле это не итеративно: как и большинство «итеративных» решений этой проблемы в сети, это выглядит так, как будто это так, но это не так. Причина, по которой это не так, заключается в том, что скелет iter функции выглядит так

1. если бла
   • рекурсия по первому элементу списка
   • в противном случае сделайте что-нибудь другое
2. если другое бла
   • выполните итерацию по остальной части списка

И самое главное, что и (1), и (2) всегда происходят, поэтому вызов в машину списка не является хвостовым вызовом: это полноценный рекурсивный вызов.

Тем не менее, вы можете сделать это намного лучше: абсолютно стандартный способ сделать это-использовать аккумулятор:

 (define (fringe l)
  (define (fringe-loop thing accum)
    (cond
      ((null? thing)
       ;; we're at the end of the list or an element which is empty list
       accum)
      ((pair? thing)
       ;; we need to look at both the first of the list and the rest of the list
       ;; Note that the order is rest then first which means the accumulator
       ;; comes back in a good order
       (fringe-loop (car thing)
                    (fringe-loop (cdr thing) accum)))
      (else
       ;; not a list at all: collect this "atomic" thing
       (cons thing accum))))
  (fringe-loop l '()))
 

Обратите внимание, что при этом строится пограничный (линейный) список снизу вверх, что является естественным способом построения линейных списков с рекурсией. Чтобы достичь этого, он немного хитро упорядочивает то, как он смотрит на вещи, чтобы результаты получались в правильном порядке. Обратите также внимание, что это также не итеративно: это рекурсивно из-за (fringe-loop ... (fringe-loop ...)) вызова. Но на этот раз все гораздо яснее.

Причина, по которой он не является итеративным, заключается в том, что процесс поиска (древовидного, Lisp) списка не является итеративным: это то, что SICP назвал бы «рекурсивным процессом», потому что (древовидные) списки Lisp рекурсивно определены как в их первом, так и в остальных полях. Ничто из того, что вы можете сделать, не сделает процесс итеративным.

Но вы можете сделать код итеративным на уровне реализации, явно управляя стеком, тем самым превращая его в хвостовую рекурсивную версию. Однако характер вычислительного процесса не меняется:

 (define (fringe l)
  (define (fringe-loop thing accum stack)
    (cond
      ((null? thing)
       ;; ignore the () sentinel or () element
       (if (null? stack)
           ;; nothing more to do
           accum
           ;; continue with the thing most recently put aside
           (fringe-loop (car stack) accum (cdr stack))))
      ((pair? thing)
       ;; carry on to the right, remembering to look to the left later
       (fringe-loop (cdr thing) accum (cons (car thing) stack)))
      (else
       ;; we're going to collect this atomic thing but we also need 
       ;; to check the stack
       (if (null? stack)
           ;; we're done
           (cons thing accum)
           ;; collect this and continue with what was put aside
           (fringe-loop (car stack) (cons thing accum) (cdr stack))))))
  (fringe-loop l '() '()))