Схема - найти наиболее глубоко вложенные списки

Question

Мне нужно найти листья в списке на схеме.

Например, если у меня есть (1 (2 3) (4 (5) (7 (8) (10 11 12)))))), мои листья будут (8) и (10 11 12).Поэтому моя функция вернет (1 (2 3) (4 (5) (7 leaf1 leaf2))))).

Определение: лист - это элемент с максимально глубокой вложенностью.

Примеры: В (1 (2 (3))) элемент (3) является листом.

В ((1 2) (3 4)) элементы (1 2) и (3 4) являются листьями.

Я попытался использовать функцию map, которая проверит, составлен ли список из списков.Если это так - я снова вызываю функцию, а если нет, я ломаю и изменяю списки на символы листьев.Это не работает.

Я застрял на нем 2 дня.Я пытаюсь найти идею, не реализация. Спасибо.

Answer 1

Это немного сложно, чтобы получить право.Вот несколько советов о том, как это сделать:

Как уже говорилось, проблема состоит в том, чтобы обходить список, находя наиболее глубоко вложенные списки, которые не содержат никаких других списков (их иногда называют "списками").атомов ") и заменяя их чем-то другим.Это можно сделать в одной рекурсивной функции, но я думаю, что проще разобрать ее на части:

1. Сначала нам нужен предикат (функция, возвращающая логическое значение #tили #f), чтобы определить, является ли список списком атомов.(Иногда это называется lat?).Вы можете написать это как простую рекурсивную функцию или использовать библиотечные функции any и list?

2. Тогда нам нужна функция (define (max-lat-depth lst) ...)чтобы выяснить, насколько глубоко вложен самый глубоко-вложенный список атомов в его аргументе.Это будет дважды рекурсивная функция - она ​​должна проверять first каждого списка, а также все элементы в rest.Мы можем определить max-lat-depth следующим образом:

   a.Если аргумент сам по себе lat, максимальная глубина равна нулю, поэтому (max-lat-depth '(1 2 3)) == 0

   b.Если первый элемент аргумента не является списком, он не может повлиять на максимальную глубину вложения.Таким образом, в этом случае max-lat-depth всего аргумента будет таким же, как max-lat-depth rest (cdr) списка: (max-lat-depth '(1 (2 (3 4))) == (max-lat-depth '((2 (3 4))) == 2

   с.Сложный случай: если первый элемент аргумента является списком (как в ((1 2) (3 4))), нам нужно будет повторить как first (или car), так и rest (или cdr)lst, возвращая максимум этих значений.Однако нам нужно добавить 1 к одному из этих двух результатов, прежде чем брать максимум.Я позволю вам выяснить, какой и почему.

3. Наконец, мы напишем функцию (define (replace-lats-at-depth depth lst r) ...), которая получит глубину вложения, возвращаемую из max-lat-depth, список lst и замена r.Он вернет копию lst, где все списки атомов на глубине depth были заменены на r.Например:

(replace-lats-at-depth 0 '(1 2 3) '*) == '*

(replace-lats-at-depth 1 '(1 (2) 3) '*) == '(1 * 3).

Как и max-lat-depth, replace-lats-at-depth повторяется как для first, так и rest из lst.Он вызовет cons в результате своих рекурсивных вызовов для построения новой древовидной структуры.Также как max-lat-depth, у него есть несколько случаев, и ему нужно будет вычесть 1 из depth в одном из своих рекурсивных вызовов.

После того, как у вас будет работать replace-lats-at-depth для заменывложенные списки с постоянным значением r, не должно быть слишком сложно улучшить его с помощью функции, которая выдает leaf1, leaf2 и т. д., как в исходном примере.

Я надеюсьэто полезно, не говоря слишком много.Дайте мне знать, если нет, и я могу попытаться уточнить.