Построение встроенной функции фильтра с помощью Racket

Question

Я пытаюсь создать фильтр (встроенную функцию) с помощью Racket как раз на практике.

Я создал следующий код: «нечетный»

(define (filter lista-1 check-function) 
(define (fil-iter lista-1 check-function lista-2) 
    (cond ((null? lista-1) lista-2) 
     ((check-function (car lista-1)) (fil-iter (cdr lista-1) check-function (append lista-2 (list (car lista-1))))) 
     (else (fil-iter (cdr lista-1) check-function lista-2)))) 
    (trace fil-iter) 
    (fil-iter lista-1 check-function '())) 

Я сделал несколько тестов с «даже?» и "номер?" как «контрольная функция».

Все выходы были правильными. Но я, возможно, ничего не вижу ... Моя интуиция говорит, что здесь что-то не так.

Answer 1

Ваша функция верна, только она имеет сложность п ² в то время как она могла бы иметь сложность п.

Причина заключается в том, что вы используете append вместо cons построить результат, и append имеет стоимость, пропорциональное длине списка, в то время как cons имеет постоянную стоимость. Итак, если вы хотите функцию с линейной сложностью вы должны написать что-то вроде:

(define (filter lista-1 check-function) 
(define (fil-iter lista-1 check-function lista-2) 
    (cond ((null? lista-1) (reverse lista-2)) 
     ((check-function (car lista-1)) 
     (fil-iter (cdr lista-1) check-function (cons (car lista-1) lista-2))) 
     (else (fil-iter (cdr lista-1) check-function lista-2)))) 
    (fil-iter lista-1 check-function '())) 

Обратите внимание, что в конце концов результат должен быть обратным, но это не меняет сложность функции, поскольку reverse имеет линейную сложность с размером списка и выполняется только один раз, в конце функции.

Можно также упростить функцию, отметив, что параметр check-function не изменяется при каждом вызове помощника fil-iter, поэтому он может быть опущен внутри него:

(define (filter lista-1 check-function) 
(define (fil-iter lista-1 lista-2) 
    (cond ((null? lista-1) (reverse lista-2)) 
     ((check-function (car lista-1)) 
     (fil-iter (cdr lista-1) (cons (car lista-1) lista-2))) 
     (else (fil-iter (cdr lista-1) lista-2)))) 
    (fil-iter lista-1 '())) 

Answer 2

можно использовать for/list с #:when пунктом для создания функция фильтра:

(define (myfilter proc lst) 
    (for/list ((item lst) 
      #:when (proc item)) 
    item)) 

(myfilter even? '(1 2 3 4 5 6)) 
; => '(2 4 6)