ラケットを使ってフィルタ組み込み関数を構築する

Question

ラケットを使ってフィルタを組み立てようとしています。

私は次のコードを作成しました： "？奇数" "？でも、" 私はいくつかのテストを行って、

(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

あなたの機能は、それがn個の複雑さを持っている可能性がありながら、唯一それがn個²の複雑さを持って、正しいです。

の理由は、あなたが結果を構築する代わりにconsのappendを使用することで、consは一定のコストを有しているappendは、リストの長さに比例したコストを持っています。最後に結果を逆にする必要がありますが、reverseは線形複雑度を持っているので、これは機能の複雑さを変更しないことを

(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 '())) 

注：線形複雑で機能をしたいのであれば、あなたのような何かを書く必要がありますリストのサイズと比較し、関数の終わりに一度だけ実行されます。

ます。また、パラメータ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

一つは、作成するために#:when句でfor/listを使用することができますフィルタ機能：

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

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