Как сделать деструктивный фильтр! в схеме?

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

(define (filter! f s)
;;Your solution

Тестовые примеры:

(define (big x) (> x 5))

(define ints (list 1 10 3 8 4 7)) 
(define ints1 (cdr ints))


(define filtered-ints (filter! big ints))  
filtered-ints 
; expect (10 8 7) 

(eq? filtered-ints ints1) ; expect #t

Кто-нибудь может помочь, пожалуйста?


filter reverse scheme
person hash__x    schedule 24.04.2012    source источник
comment
Вы имеете в виду, что фильтр изменит список, заданный в качестве аргумента, удалив элементы, не прошедшие проверку? Какая польза от ints1 здесь?   -  person PJ.Hades    schedule 24.04.2012
comment
Я тоже не уверен, но я предполагаю, что это связано с изменением указателя в исходном списке ввода, что делает filtered-ints и ints1 эквивалентными. Вот что меня больше всего смущает.   -  person hash__x    schedule 24.04.2012
comment
возможный дубликат Сделайте разрушительный реверс! функция в схеме   -  person matt    schedule 24.04.2012
comment
@matt reverse! сильно отличается от filter!, это не повторяющийся вопрос   -  person Óscar López    schedule 24.04.2012
comment
@ÓscarLópez - о да. Моя вина. Они оба выскочили вместе, и я слишком быстро нажал кнопку закрытия.   -  person matt    schedule 24.04.2012

Ответы (1)


arrow_upward
1
arrow_downward

Это должно работать:

(define (filter! f lst)
  (let loop ((ans lst))
    (cond ((null? ans)
           ans)
          ((not (f (car ans)))
           (loop (cdr ans)))
          (else
           (scan-in f ans (cdr ans))
           ans))))

(define (scan-in f prev lst)
  (if (pair? lst)
    (if (f (car lst))
        (scan-in  f lst  (cdr lst))
        (scan-out f prev (cdr lst)))))

(define (scan-out f prev lst)
  (let loop ((lst lst))
    (if (pair? lst)
        (if (f (car lst))
            (begin (set-cdr! prev lst)
                   (scan-in  f lst (cdr lst)))
            (loop (cdr lst)))
        (set-cdr! prev lst))))

Я адаптировал приведенное выше из filter! в SRFI 1: Библиотека списков. Обратите внимание, что если вы используете Racket, необходимо изменить одну или две вещи, чтобы приведенный выше код работал правильно. Например, Racket больше не поддерживает set-cdr!, и вместо этого вам придется использовать set-mcdr!.

person Óscar López    schedule 24.04.2012