Схема: извлечение элементов из вложенных списков

Question

Я довольно новичок в Scheme, и у меня возникли проблемы с написанием функции как части домашней работы. У меня есть граф G, указанный мною в виде списка в следующем формате: ((node1 node2 weight1) (node3 node4 weight2) ...). Я пытаюсь написать функцию, которая возвращает мне список всех узлов (V) в этом графе в этом формате: (node1 node2 node3 ...). Функция может принимать только граф (G) в качестве входного сигнала.

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

(define nodes-of 
     (lambda (G) 
     (if (null? G) 
      () 
      (begin (add-to-set (cadar G) (nodes-of (cdr G))) 
        (add-to-set (caar G) (nodes-of (cdr G)))))) 

Я думаю, что это не так, хотя, как первая рекурсия включает только (кадар G), а вторая включает (caar G), а возвращаемое значение будет установлено только вторым оператором при начале (если я не ошибаюсь).

add-to-set - это функция, которую я написал ранее для домашней работы, она добавляет элемент в список, если он еще не существует в списке. (например: add-to-set n S, это добавит n к S)

Может ли кто-нибудь помочь мне с этим? (btw Мне не разрешено использовать несколько let's, let * or set)

Answer 1

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

В случае обработки списка ваш базовый регистр является пустым списком, поэтому вы хотите проверить значение null. Тогда формула сокращения будет отрывать часть списка, а затем вызывать процедуру на оставшейся части. Итак, как я уже сказал, вы близки.

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

(define nodes-of 
    (lambda (G) 
     (if (null? G) ;<-- have we reached the base case yet? 
      '()   ;<-- if yes, return null so our cons will build a list 
      (cons (caar G) (cons (cadar G) (nodes-of (cdr G))))))) ;<-- if not, keep building the list by grabbing the things we want from each element, then reducing the list 

Вы также можете использовать let, если вы хотите ..

(define nodes-of 
    (lambda (G) 
     (if (null? G) 
      '() 
      (let ((n1 (caar G)) 
        (n2 (cadar G))) 
       (cons n1 (cons n2 (nodes-of (cdr G)))))))) 

В вашем случае вы будете использовать add-to-set где я использовал cons. Как только мы дойдем до базового случая, все вызовы add-to-set будут оценены, начиная с последнего, а затем вернутся вниз к стеку.

|cons n3 '()   | 2 => (n3) 
|cons n2 [result of 2] | 1 => (n2 n3) 
|cons n1 [result of 1] | 0 => (n1 n2 n3)