Преобразование функции с двумя рекурсивными вызовами в схеме, чтобы сделать ее хвостовой рекурсивной - PullRequest
Новая
       44

Преобразование функции с двумя рекурсивными вызовами в схеме, чтобы сделать ее хвостовой рекурсивной

6 голосов
/ 21 марта 2011

Прежде чем я начну: ДА, это домашнее задание из колледжа.Прежде чем мне сказали, что я ленивый и злой: эта часть домашнего задания состояла в том, чтобы преобразовать две функции, которые у нас уже были, эта - шестая. 

(define (flatten-list a-list)
  (cond ((null? a-list) '())
      ((list? (car a-list)) 
       (append (flatten-list (car a-list)) (flatten-list (cdr a-list))))
      (else (cons (car a-list) (flatten-list (cdr a-list))))))

Функция, как вы можете догадаться, выравниваетсписок, даже если он вложенный.Моя конкретная проблема с преобразованием заключается в условии (list? (Car a-list)), в котором я делаю два рекурсивных вызова.Я уже сделал Фибоначчи, что я могу сделать, просто имея два «акуммулятора» на рекурсии хвоста.Тем не менее, мой ум еще не обучен этому, чтобы знать, как он должен идти.

Я был бы признателен, если бы мне давали подсказки, а не результат.Спасибо!

1 Ответ

6 голосов
/ 21 марта 2011

Вот мое решение: 

(define (flatten-iter a-list)
  (define (flat-do acc lst-interm lst)
    (cond 
      ((null? lst)
       (reverse acc))
      ((and (list? lst-interm) (not (null? lst-interm)))
       (flat-do acc (car lst-interm) (append (cdr lst-interm) lst)))
      ((not (list? lst-interm))
       (flat-do (cons lst-interm acc) empty lst))
      ((list? (car lst))
       (flat-do acc (car lst) (cdr lst)))
      (else
       (flat-do (cons (car lst) acc) empty (cdr lst)))))
  (flat-do empty empty a-list))

(flatten-iter (list 1 (list 2 (list 3 4 (list 5 empty 6))) 7 8))
=> (1 2 3 4 5 6 7 8)

Хвост-рекурсивные функции требуют, чтобы они никогда не возвращались, и поэтому вы не можете использовать стек для хранения состояния вашей программы.Вместо этого вы используете аргументы функции для передачи состояния между вызовами функций.Поэтому нам нужно определить, как сохранить состояние.Поскольку результатом нашей функции является list?, имеет смысл увеличить список empty;мы используем acc для этой цели.Вы можете увидеть, как это работает в ветке else выше.Но мы должны иметь возможность обрабатывать вложенные списки.И пока мы углубляемся, мы должны сохранить остальные элементы вложенного списка для дальнейшей обработки.Пример списка: (list 1 (list 2 3) 4 5)

До (list 2 3) мы уже добавили 1 в аккумулятор.Поскольку мы не можем использовать стек, нам нужно другое место для хранения остальных элементов списка.И это место является аргументом lst, который содержит элементы исходного списка, которые должны быть сведены.Мы можем просто append lst к остальным элементам (cdr (list 2 3)), которые (list 3), и продолжить с головой списка, на которую мы наткнулись при выравнивании, то есть (car (list 2 3)), которая является просто 2,Теперь (and (list? lst-interm) (not (null? lst-interm))) выполняется успешно, потому что flat-do вызывается следующим образом: 

(flat-do (list 1) (list 2 3) (list 4 5))

и условие вызывает этот код: 

(flat-do (list 1) (car (list 2 3)) (append (cdr (list 2 3)) (list 4 5)))

flat-do снова вызывается следующим образом: (flat-do (список 1) 2 (список 3 4 5))

Условие (not (list? 2)) теперь успешно выполняется и код (flat-do (cons 2 1) empty (list 3 4 5)) оценивается.

Остальная обработка выполняется с помощью else ветвь, пока lst не станет null? и reverse не будет выполнено acc.Затем функция возвращает реверсированный аккумулятор.

...