Как удалить все повторяющиеся элементы в схеме списка?

#scheme

#схема

Вопрос:

Моя попытка была,

 (define (remove-dup lst)
  (cond ((null? lst) '())
        ((null? (cdr lst)) (car lst))
        ((equal? (car lst) (car (cdr lst))) (remove-dup (cdr lst)))
        (else (cons (car lst) (remove-dup (cdr lst))))
        )

  )

Мой список был (a b c a a c c c )
Чего я хочу, так это (a b c) . Есть идея?

Спасибо,

1. Попробуйте пройти шаг за шагом, что происходит при первом вызове — в какой cond ветке вы окажетесь?

2. @Anders Lindahl: Я тестировал это с помощью своего отладчика, но я не мог понять, где я пропустил. Хотя мне это показалось разумным. Не могли бы вы дать еще несколько советов?

Ответ №1:

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

 (define (remove-dup ls)
  (let loop ((ls ls) (seen '()))
     (cond
       ((null? ls) '())
       ((memq (car ls) seen) (loop (cdr ls) seen))
       (else (cons (car ls) (loop (cdr ls) (cons (car ls) seen))))))

Обновлено с учетом ваших комментариев — вероятно, это не самое чистое решение, но должно дать вам представление о том, как оно может работать.

 (define (rdup ls)
  (let loop ((ls ls) (current #f)) ; this is bad coding style, a "magic" variable you don't expect to see in your list
     (cond
       ((null? ls) '())
       ((null? (cdr ls)) (if (eq? (car ls) current) '() ls))
       ((eq? (car ls) (cadr ls)) (loop (cdr ls) (car ls)))
       ((eq? (car ls) current) (loop (cdr ls) current))
       (else (cons (car ls) (loop (cdr ls) (car ls)))))))

1. @A Lee: Спасибо. Не волнуйтесь, это не было моим домашним заданием. Кроме того, я ищу рекурсивное решение вместо итеративного, поскольку причина, по которой я перешел на Scheme, заключается в улучшении моей рекурсивной мысли.

2. Рад это слышать. Я бы определенно рекомендовал использовать отладчик (или трассировку с помощью pencil amp; paper, как мне приходилось делать это в колледже), чтобы лучше понять, как рекурсивные вызовы создаются внутри цикла и как его аргументы меняются с каждым вызовом.

3. @A Lee: Мой ответ был очень, очень близок, в одном шаге от ответа, который я думаю. Тем не менее, я все еще не смог разобраться. Кстати, ваш ответ немного отличался от того, который я ожидал. В приведенном выше примере результат правильный. Однако для a b a a c c он должен возвращать a b вместо a b c . Это была моя ошибка, поскольку я не указал это четко.

4. Ах, так '(a b a b a b) следует ли вернуть '(a b a b a b) ?

5. @A Lee: О да, еще бы! Однако я хотел бы увидеть рекурсивное решение. Вы не возражаете? потому что без рекурсии я не чувствую мотивации изучать Scheme.

Ответ №2:

R5RS SRFI1

 (define (remove-duplicates lst)
    (fold-right (lambda (f r)
             (cons f (filter (lambda (x) (not (equal? x f))) r))) '() lst))

Ответ №3:

Используя SRFI 1, вы можете использовать напрямую delete-duplicates или delete-duplicates! : http://srfi.schemers.org/srfi-1/srfi-1.html#delete-duplicates