Как реализован фильтр?

Question

Нужна помощь по этому вопросу с использованием функции схемы. Возвращает список, содержащий все элементы данного списка, которые удовлетворяют данному предикату.Например, (filter (lambda (x) (< x 5)) '(3 9 5 8 2 4 7)) должно вернуть (3 2 4).

Answer 1

filterb - на всякий случай уже есть функция с именем filter.

(define filterb
    (lambda (pred lst)
      (cond ((null? lst) '())
            ((pred (car lst)) (cons (car lst) (filterb pred (cdr lst))))
            (else (filterb pred (cdr lst))))))

Вот она, хотя я уверен, что она может выглядеть лучше.

Answer 2

Простой способ написать filter процедуру:

(define (my-filter pred lst)
  (cond ((null? lst) null)
        ((pred (first lst))
         (cons (first lst) (my-filter pred (rest lst))))
        (else (my-filter pred (rest lst)))))

Обратите внимание, что я назвал процедуру my-filter, потому что встроенная процедура с именем filter уже существует, и не стоит перезаписывать ее определение.

Answer 3

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

(define (filter pred? list)
  (define (filter-aux result current-pair xs)
    (cond ((null? xs)
           result)
          ((pred? (car xs))
           (set-cdr! current-pair
                     (cons (car xs)
                           '()))
           (filter-aux result
                       (cdr current-pair)
                       (cdr xs)))
          (else
           (filter-aux result
                       current-pair
                       (cdr xs)))))
  (let ((init (cons 'throw-me-out '())))
    (filter-aux (cdr init) init list)))

Или, используя синтаксис let loop:

(define (filter pred? xs)
  (let ((result (cons 'throw-me-out '()))
        (xs xs))
    (let loop ((current-pair result))
      (cond ((null? xs)
             (cdr result))
            ((pred? (car xs))
             (set-cdr! current-pair
                       (cons (car xs) '()))
             (loop (cdr current-pair) (cdr xs)))
            (else
             (loop current-pair (cdr xs)))))))

Answer 4

Для альтернативной хвостовой рекурсии filter, которая не требует изменяемых списков, вы можете использовать что-то вроде этого:

(define (my-filter f lst)
  (define (iter lst result)
    (cond
      ((null? lst) (reverse result))
      ((f (car lst)) (iter (cdr lst)
                           (cons (car lst) result)))
      (else (iter (cdr lst)
                  result))))
  (iter lst '()))

Обратное действие требует, чтобы вы прошли список еще раз, но это можетбыть реализовано за время O (n) с постоянным пространством стека в неизменяемых списках, поэтому общее время по-прежнему равно O (n).

Answer 5

Попробуйте определить filter в качестве экземпляра правого сгиба:

(define (my-filter op xs)
        (fold-right
           (lambda (next result) ...)
           '()
           xs))

Подсказка: используйте if и cons